本文主要是介绍Codeforces Round #286 (Div. 2) C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
友情链接
题意：0到30000的一条直线上面有一些东西可以收集，有些地方有，有些地方没有，给定第一次（即前一次）跳跃的距离l，下一次每次跳跃可以跳前面的距离l-1，l，l+1，问跳到不能跳的时候最后可以收集多少东西？
思路;动态规划，定义dp[i][j]表示到了第i个位置与第一次跳的距离相差j最多可以收集多少。由于有负数，我引入了300的偏移量，因为最后的跳跃的次数最多不会超过250，然后方程就可以转移了。
ps：开始的时候写成了递归的形式，无限超时，后来改成了递推的形式就过了，作死的啊！动态规划还是这么弱！！！！！！！！！！！
#include <bits/stdc++.h>
using namespace std;
const int MM=60005;
const long long MOD=1000000007;
int n,d;
int ans=0;
int maxn=0;
int num[MM];
int dp[MM][600];
int main()
{scanf("%d%d",&n,&d);memset(dp,-1,sizeof(dp));///定义没有的状态表示成-1memset(num,0,sizeof(num));for(int i=0;i<n;i++){int x;scanf("%d",&x);num[x]++;maxn=max(maxn,x);}ans=dp[d][300]=num[d];for(int i=d;i<=maxn;i++){for(int j=0;j<600;j++){if(dp[i][j]==-1)continue;int l=d+(j-300);///获得上一次跳跃的距离if(l<=0)continue;if(l-1>0)dp[i+l-1][j-1]=max(dp[i+l-1][j-1],dp[i][j]+num[i+l-1]);dp[i+l][j]=max(dp[i+l][j],dp[i][j]+num[i+l]);dp[i+l+1][j+1]=max(dp[i+l+1][j+1],dp[i][j]+num[i+l+1]);ans=max(ans,max(dp[i+l-1][j-1],max(dp[i+l][j],dp[i+l+1][j+1])));}}cout<<ans<<endl;return 0;
}
这篇关于Codeforces Round #286 (Div. 2) C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
