首页 > 代码库 > Codeforces Round #286 (Div. 1) A. Mr. Kitayuta, the Treasure Hunter DP
Codeforces Round #286 (Div. 1) A. Mr. Kitayuta, the Treasure Hunter DP
链接：
http://codeforces.com/problemset/problem/506/A
题意：
给出30000个岛，有n个宝石分布在上面，第一步到d位置，每次走的距离与上一步的差距不大于1，问走完一路最多捡到多少块宝石。
题解：
容易想到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了。
代码：
31 int n, d;32 int a[MAXN];33 int dp[MAXN][500];34 35 int main() {36 ios::sync_with_stdio(false), cin.tie(0);37 cin >> n >> d;38 while (n--) {39 int x;40 cin >> x;41 a[x]++;42 }43 memset(dp, -1, sizeof(dp));44 dp[d][250] = a[d];45 int ans = a[d];46 rep(i, d, 30001) rep(j, 1, 500) {47 if (dp[i][j] == -1) continue;48 int to = i + d + j - 250;49 if (to <= 30000) {50 dp[to][j] = max(dp[to][j], dp[i][j] + a[to]);51 ans = max(ans, dp[to][j]);52 }53 if (to + 1 <= 30000) {54 dp[to + 1][j + 1] = max(dp[to + 1][j + 1], dp[i][j] + a[to + 1]);55 ans = max(ans, dp[to + 1][j + 1]);56 }57 if (to <= 30000 && to - i > 1) {58 dp[to - 1][j - 1] = max(dp[to - 1][j - 1], dp[i][j] + a[to - 1]);59 ans = max(ans, dp[to - 1][j - 1]);60 }61 }62 cout << ans << endl;63 return 0;64 }
Codeforces Round #286 (Div. 1) A. Mr. Kitayuta, the Treasure Hunter DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。