首页 > 代码库 > Codeforces Round #286 Div.1 A Mr. Kitayuta, the Treasure Hunter --DP
Codeforces Round #286 Div.1 A Mr. Kitayuta, the Treasure Hunter --DP
题意：0~30000有30001个地方，每个地方有一个或多个金币，第一步走到了d，步长为d，以后走的步长可以是上次步长+1,-1或不变，走到某个地方可以收集那个地方的财富，现在问走出去(>30000)之前最多可以收集到多少财富。
解法：容易想到DP，dp[i][j]表示到达 i 处，现在步长为 j 时最多收集到的财富，转移也不难,cnt[i]表示 i 处的财富。
dp[i+step-1] = max(dp[i+step-1],dp[i][j]+cnt[i+step+1])
dp[i+step] = max(dp[i+step],dp[i][j]+cnt[i+step])
dp[i+step+1] = max(dp[i+step+1],dp[i][j]+cnt[i+step+1])
但是步长直接开30000存的话肯定是不行的，又发现，其实走过30000之前，步长的变化不会很大，如果步长每次增加1的话，那么最少1+2+...+n=n(n+1)/2 > 30000, n<250，即步长变化不会超过250.所以第二维保存相对原始步长的改变量，-250~250，开500就够了，这样就不会MLE了。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;#define N 10007int dp[3*N][507];int cnt[3*N],ans;int main(){ int i,j,n,d; while(scanf("%d%d",&n,&d)!=EOF) { memset(cnt,0,sizeof(cnt)); for(i=1;i<=n;i++) { scanf("%d",&j); cnt[j]++; } memset(dp,-1,sizeof(dp)); dp[d][250] = cnt[d]; ans = dp[d][250]; for(i=d;i<=30000;i++) { for(j=1;j<=500;j++) { if(dp[i][j] == -1) continue; int to = i+d+j-250; if(to <= 30000) { dp[to][j] = max(dp[to][j],dp[i][j]+cnt[to]); ans = max(ans,dp[to][j]); } if(to+1 <= 30000) { dp[to+1][j+1] = max(dp[to+1][j+1],dp[i][j]+cnt[to+1]); ans = max(ans,dp[to+1][j+1]); } if(to <= 30000 && to-i > 1) { dp[to-1][j-1] = max(dp[to-1][j-1],dp[i][j]+cnt[to-1]); ans = max(ans,dp[to-1][j-1]); } } } cout<<ans<<endl; } return 0;}
Codeforces Round #286 Div.1 A Mr. Kitayuta, the Treasure Hunter --DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。