题目链接:
题意: 中文题诶~
思路: dp
1 <= n, d <= 3e4, 直接用 dp[i][j] 存储从上一个岛屿经过 距离 j 到达岛屿 i 的最大收获显然是不行的. 可以令 j' 为当前移动距离 j 与 d 的差值, 即 dp[i][j'] 存储从上一个岛屿经过距离 |j' + d| 到达岛屿 i 最大收获. 因为 d 每次只能加或者减 1, 所以偏移量 j' 的范围在 -250 ~ 250 之间. 可以给所有偏移量加 300 使其全部变成正数, 后面计算时再减回去即可. 那么动态转移方程为:
int next = i + j + d - 300;
if(next < MAXN && next - i) dp[next][j] = max(dp[next][j], dp[i][j] + vis[next]);
if(next + 1 < MAXN && next - i + 1) dp[next + 1][j + 1] = max(dp[next + 1][j + 1], dp[i][j] + vis[next + 1]);
if(next - 1 >= 1 && next < MAXN && next - i - 1 >= 1) dp[next - 1][j - 1] = max(dp[next - 1][j - 1], dp[i][j] + vis[next - 1]);
代码:
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int MAXN = 3e4 + 1; 7 int dp[MAXN][610], vis[MAXN];//dp[i][j]存储从上一个岛屿经过距离|j+d|到达岛屿i最大收获,其中j为当前移动步数与d的差值 8 9 int main(void){10 int n, d, x;11 memset(dp, -1, sizeof(dp));12 scanf("%d%d", &n, &d);13 for(int i = 0; i < n; i++){14 scanf("%d", &x);15 vis[x]++;16 }17 dp[d][300] = vis[d];//所有偏移量+300,但是其他dp值为0,所以不必额外处理18 int ans = vis[d];19 for(int i = 1; i < MAXN; i++){20 for(int j = 0; j < 600; j++){21 if(dp[i][j] == -1) continue;22 int next = i + j + d - 300;//这里的j表示+300后的偏移量,所以要减回去23 if(next < MAXN && next - i){24 dp[next][j] = max(dp[next][j], dp[i][j] + vis[next]);25 ans = max(ans, dp[next][j]);26 }27 if(next + 1 < MAXN && next - i + 1){28 dp[next + 1][j + 1] = max(dp[next + 1][j + 1], dp[i][j] + vis[next + 1]);29 ans = max(ans, dp[next + 1][j + 1]);30 }31 if(next - 1 >= 1 && next < MAXN && next - i - 1 >= 1){32 dp[next - 1][j - 1] = max(dp[next - 1][j - 1], dp[i][j] + vis[next - 1]);33 ans = max(ans, dp[next - 1][j - 1]);34 }35 }36 }37 cout << ans << endl;38 return 0;39 }