首页 > 其他分享 >牛客动态规划1选做

牛客动态规划1选做

时间：2023-04-19 19:22:31浏览次数：54  
标签：ch int long 牛客 选做 include && 动态 getchar

[NOIP2002]过河卒

题目链接

进行记忆化搜索，然后强制把马所在的点和控制的点赋值为 0

#include<bits/stdc++.h>
#define int long long
using namespace std;

set<pair<int,int>> st;

int f[25][25];

int calc( int x , int y ){
    if( x == 0 && y == 0 ) return f[x][y] = 1;
    if( x < 0 || y < 0 ) return 0;
    if( st.count( {x,y} ) ) return 0;
    if( f[x][y] ) return f[x][y];
    return f[x][y] = calc( x - 1 , y ) + calc( x , y - 1 );
}

int32_t main() {
    int n , m , s , t;
    cin >> n >> m >> s >> t;
    st.insert( { s , t } );
    st.insert( { s-1 , t-2 } ) ,st.insert( { s-1 , t+2 } );
    st.insert( { s+1 , t-2 } ) ,st.insert( { s+1 , t+2 } );
    st.insert( { s-2 , t-1 } ) ,st.insert( { s-2 , t+1 } );
    st.insert( { s+2 , t-1 } ) ,st.insert( { s+2 , t+1 } );
    cout << calc( n , m ) << "\n";
    return 0;
}

[NOIP2008]传球游戏

题目链接

设状态f[i][j]表示第j次传球后，球在i手上的点方案数，则f[i][j]=f[i-1][j-1]+f[i+1][j-1]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int  N = 35;
int f[N][N] , n , m;

int32_t main() {
    cin >> n >> m;
    f[1][0] = 1;
    for( int j = 1 ; j <= m ; j ++ ){
        f[1][j] = f[n][j-1] + f[2][j-1];
        f[n][j] = f[1][j-1] + f[n-1][j-1];
        for( int i = 2 ; i < n ; i ++ )
            f[i][j] = f[i-1][j-1] + f[i+1][j-1];
    }
    cout << f[1][m] << "\n";

    return 0;
}

滑雪

题目链接

记忆化搜索一下，f[x][y]表示从(x,y)出发最远可以走多远。

每次只能从相邻且比当前低的点转移过来

#include<bits/stdc++.h>

using namespace std;

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}


const int N = 105;
const int dx[] = { 0 , 0 , 1 , -1 } , dy[] = { 1 , -1 , 0 , 0 };
int n , m , h[N][N] , f[N][N] , res = INT_MIN;

int dfs( int x , int y ){
    if( x < 1 || y < 1 || x > n || y > m ) return 0;
    if( f[x][y] ) return f[x][y];
    f[x][y] = 1;
    for( int i = 0 , fx , fy ; i < 4 ; i ++ ){
        fx = x + dx[i] , fy = y + dy[i];
        if( h[x][y] > h[fx][fy] ) f[x][y] = max( f[x][y] , dfs( fx , fy ) + 1 );
    }
    return f[x][y];
}

int32_t main() {
    n = read() , m = read();
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= m ; j ++ )
            h[i][j] = read();
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= m ; j ++ )
            res = max( res , dfs( i , j ) );
    cout << res;
    return 0;
}

方块与收纳盒

https://ac.nowcoder.com/acm/contest/24213/1001

简单的斐波那契额数列

递推版

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

ll f[100];

int32_t main() {
    f[0] = f[1] = 1;
    for( int i = 2 ; i <= 80 ; i ++ ) f[i] = f[i-1] + f[i-2];
    for( int t = read() , x ; t ; t -- )
        x = read() , cout << f[x] << "\n";
    return 0;
}

递归版

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

ll f[100];

ll calc( int x ){
    if( f[x] ) return f[x];
    return f[x] = calc( x - 1 ) + calc( x - 2 );
}

int32_t main() {
    f[0] = f[1] = 1;
    for( int t = read() , x ; t ; t -- )
        x = read() , cout << calc(x) << "\n";
    return 0;
}

舔狗舔到最后一无所有

https://ac.nowcoder.com/acm/contest/24213/1002

设f[i]表示前i天的合法方案。

如果i天与i-1天不同，则有两种选择方法

如果i天与i-1天相同，就不能与i-2天相同，与i-2天不同有两种选择方法

所以f[i] = f[i-1] * 2+ f[i-2]*2 

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5+5 , mod = 1e9+7;
int f[N];
int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

int32_t main() {
    f[1] = 3 , f[2] = 9;
    for( int i =3 ; i < N ; i ++ )
        f[i] = ( f[i-1] + f[i-2] ) % mod * 2 % mod;
    for( int t = read() , x ; t ; t -- )
        x = read() , cout << f[x] << "\n";
    return 0;
}

[NOIP2001]装箱问题

https://ac.nowcoder.com/acm/contest/24213/1017

f[i][j]表示前i个物品能否填满空间j这样就可以得到状态转移方程f[i][j] |= f[i-1][j-v]

然后可以通过倒序枚举的方式优化一维空间

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int N = 20005;
bool f[N];

int main(){
    int v , n; cin >> v >> n;
    f[0] = 1;
    for( int i = 1 , x ; i <= n ; i ++ ){
        cin >> x;
        for( int i = v ; i >= x ; i -- )
            f[i] |= f[i-x];
    }
    for( int i = v ; i >= 0 ; i -- )
        if( f[i] ) cout << v-i , exit(0);
    return 0;
}

可爱の星空

因为合并的时候肯定是尽可能接近的两个数合并才可以使话费尽可能的小，所以为了合成n必须先合成n/2，然后处理一下奇数的情况就好

#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

map< int , int > g;

int f( int x ) {
    if( x == 1 || x == 2 ) return 0;
    if( g[x] != 0 ) return g[x];
    return g[x] = f(x/2) + f( x/2 + (x&1)) + (x&1);
}

void solve(){
    int n = read();
    cout << f(n) << "\n";
}


int32_t main() {
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

数字三角形

#include<bits/stdc++.h>
using namespace std;


int32_t main() {
    int n; cin >> n;
    for( int i = 1 , t = 1 ; i <= n ; i ++ ){
        for( int j = 1 ; j <= i ; j ++ , t ++ )
            cout << setw(4) << t;
        cout << "\n";
    }
    return 0;
}

[NOIP2005]采药

https://ac.nowcoder.com/acm/contest/24213/1018

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> f( n+1 , INT_MIN );
	f[0] = 0;
	for( int v , w ; m ; m -- ){
		cin >> v >> w;
		for( int i = n ; i >= v ; i -- )
			f[i] = max( f[i] , f[i-v] + w);
	}
	cout << *max_element(f.begin(), f.end());	
	return 0;
}

[NOIP2004]合唱队形

求两边最长上升子序列，枚举中间点

#include<bits/stdc++.h>

using namespace std;

#define int long long

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

int32_t main() {
    int n = read();
    vector<int> a(n+1) , f(n+1 , 1 ) , g(n+1 , 1 );
    for( int i = 1 ; i <= n ; i ++ ) a[i] = read();
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j < i ; j ++ )
            if( a[j] < a[i] ) f[i] = max( f[i] , f[j] + 1 );
    for( int i = n ; i >= 1 ; i -- )
        for( int j = n ; j > i ; j -- )
            if( a[j] < a[i] ) g[i] = max( g[i] , g[j] + 1 );
    int res = INT_MIN;
    for( int i = 1 ; i <= n ; i ++ )
        res = max( res , f[i] + g[i] - 1);
    cout << n - res << "\n";
    return 0;
}

标签：ch,int,long,牛客,选做,include,&&,动态,getchar
From： https://www.cnblogs.com/PHarr/p/17334378.html

相关文章

  • Jsp动态显示服务器时间
    <scriptlanguage="javascript"> varcurrentDate=newDate(<%=newjava.util.Date().getTime()%>); functionrun(){ currentDate.setSeconds(currentDate.getSeconds()+1); document.getElementById("currentTime&qu......
  • 动态拨号代理池的应用场景与实现原理解析
    随着互联网的发展和应用场景的不断扩大，数据采集和爬虫技术也日渐成为一项重要的任务。然而，很多网站为了保护自身权益，设置了严格的反爬虫策略，让数据采集变得更加困难。在这种情况下，动态拨号代理池成为了解决方案之一。动态拨号代理池的应用场景动态拨号代理池主要在以下几方......
  • 动态拨号技术在数据采集中的应用及实现方案介绍
    随着互联网的兴起，数据采集逐渐成为了一个越来越重要的领域。然而，随着互联网的不断演进和站点反爬虫技术的不断更新，传统的静态代理技术逐渐失去了其优势，被动态拨号技术所取代。那么，动态拨号技术在数据采集中究竟有哪些应用呢？又如何去实现呢？一、动态拨号技术在数据采集中的应......
  • 如何使用动态拨号代理提高网络爬虫成功率
    随着互联网的不断发展和数据的爆炸增长，越来越多的企业和个人开始使用网络爬虫来获取所需的数据。然而，在爬虫过程中，很容易被目标站点识别并拦截，导致数据抓取失败。为了解决这一问题，许多开发者开始使用动态拨号代理技术来提高网络爬虫的成功率。动态拨号代理是一种常用的技术......
  • SchemaRegestry组件原生的类和方法无法实现flink消费kafka的数据动态调整schema的情况
    0、前提知识储备Conflurent公司的SchemaRegestry组件的基本了解和使用一、背景：0.组件版本flink：1.141.链路调整情况原先链路：oracle-->OGG-->kafka-->flink-->数据库\湖\仓实现链路：oracle-->OGG-->kafka（搭配conflurent公司的SchemaRegestry组件使用）-->flink-->数据库\湖\仓2......
  • 动态指定DataGrid中多个参数的超链接列
    动态指定DataGrid中多个参数的超链接列<scriptlanguage="javascript"type="text/javascript">document.title="动态指定DataGrid中多个参数的超链接列(downmoon)-"+document.title</script>.net自带的DataGrid超链接列只能指定一个动态参数，可以通过以下方式来改进：第一......
  • 动态规划问题总结
    背包问题参考：希望用一种规律搞定背包问题分类排列组合问题\[dp[i]+=dp[i-num[j]]\]判断问题（trueorfalse）\[dp[i]=dp[i]||dp[i-num[j]]\]最大最小问题\[dp[i]=min(dp[i],dp[i-num[j]]+1)\]或者\[dp[i]=max(dp[i],dp[i-num[j]]+1)\]判定与步骤......
  • 174_技巧_Power BI 动态格式(万|亿)
    174_技巧_PowerBI动态格式(万|亿)一、背景PowerBI2023年4月份更新，新增加了一个预览功能：动态格式(Dynamicformatstringsformeasures)，度量值的结果可以动态的显示为不同的格式。今天我们主要来看一个技巧，如何在PowerBI动态的根据数值的大小显示单位为万或者亿。Power......
  • xor (牛客多校) (线性基+ 线段树)
      思路:问xor起来有没有某个值,想到线性基然后发现问L-R区间的集合都要表示x,利用线性基的交集解决在利用线段树解决区间问题 #include<iostream>usingnamespacestd;typedefunsignedintui;constintmaxn=50005;structL_B{//线性基结构体ui......
  • 小白用chatgpt编写python 爬虫程序代码 抓取网页数据(js动态生成网页元素)
    jS动态生成，由于呈现在网页上的内容是由JS生成而来，我们能够在浏览器上看得到，但是在HTML源码中却发现不了一、注意：代码加入了常规的防爬技术    如果不加，如果网站有防爬技术，比如频繁访问，后面你会发现什么数据都取不到1.1 模拟请求头： 这里入进入一步加强，随机，主要是User-Agen......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99