题目链接：CF#286 - A
这场CF就这样爆零了...我真是太蒟蒻了...
题目分析
比赛的时候看到A题就发现不会，之后一直也没想出来，于是就弃了，还好不提交也不掉Rating...
比赛后看评论，看到有人说“I could not even solve the problem A, shame on me.” ，立刻就感觉到我是多么的蒟蒻...
看了评论中有人发的题解，就一句 “Normal DP”，再看了他的简单的解释，这才恍然大悟...
这道题就可以使用普通的DP，用 f[i][j] 表示走到第 i 个位置，上一步跳了 j 的距离的最大收益，直接这样做的话，i j 的范围都会是 30000 的，然而我们可以发现重要的一点， j 相对于初始跳跃距离 d 的上下波动不会超过 300 ！因为假如它波动超过 300，就至少要连续跳 300 次递减或递增的距离，这个距离和一定会超过 30000，所以这个 j 的范围只要开 600 就可以了。
然后就完全是 “Normal DP” 了..
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std; const int MaxN = 30000 + 5, MaxM = 600 + 5, INF = 999999999; int n, d, Ans;
int V[MaxN], f[MaxN][MaxM]; inline int gmax(int a, int b) {return a > b ? a : b;} int main()
{
scanf("%d%d", &n, &d);
int a;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a);
++V[a];
}
Ans = V[d];
for (int i = 0; i <= 30000; ++i) {
for (int j = 0; j <= 601; ++j) {
f[i][j] = -INF;
}
}
f[d][301] = V[d];
for (int i = d + 1; i <= 30000; ++i) {
for (int j = 1; j <= 600; ++j) {
if (i - (j - 301 + d) < 0 || i - (j - 301 + d) >= i) continue;
f[i][j] = gmax(f[i][j], f[i - (j - 301 + d)][j]);
f[i][j] = gmax(f[i][j], f[i - (j - 301 + d)][j + 1]);
f[i][j] = gmax(f[i][j], f[i - (j - 301 + d)][j - 1]);
f[i][j] += V[i];
Ans = gmax(Ans, f[i][j]);
}
}
printf("%d\n", Ans);
return 0;
}