题目链接: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1455

题意: 中文题诶~

思路: 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]);

代码:

 #include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std; const int MAXN = 3e4 + ;
int dp[MAXN][], vis[MAXN];//dp[i][j]存储从上一个岛屿经过距离|j+d|到达岛屿i最大收获,其中j为当前移动步数与d的差值 int main(void){
int n, d, x;
memset(dp, -, sizeof(dp));
scanf("%d%d", &n, &d);
for(int i = ; i < n; i++){
scanf("%d", &x);
vis[x]++;
}
dp[d][] = vis[d];//所有偏移量+300,但是其他dp值为0,所以不必额外处理
int ans = vis[d];
for(int i = ; i < MAXN; i++){
for(int j = ; j < ; j++){
if(dp[i][j] == -) continue;
int next = i + j + d - ;//这里的j表示+300后的偏移量,所以要减回去
if(next < MAXN && next - i){
dp[next][j] = max(dp[next][j], dp[i][j] + vis[next]);
ans = max(ans, dp[next][j]);
}
if(next + < MAXN && next - i + ){
dp[next + ][j + ] = max(dp[next + ][j + ], dp[i][j] + vis[next + ]);
ans = max(ans, dp[next + ][j + ]);
}
if(next - >= && next < MAXN && next - i - >= ){
dp[next - ][j - ] = max(dp[next - ][j - ], dp[i][j] + vis[next - ]);
ans = max(ans, dp[next - ][j - ]);
}
}
}
cout << ans << endl;
return ;
}

最新文章

  1. HDU5887 Herbs Gathering(2016青岛网络赛 搜索 剪枝)
  2. 广播后刷新界面-调用其他界面的方法触动广播后刷新该界面UI
  3. 在html 中嵌入优酷视频
  4. sqlserver 查询库中有多少张表
  5. 模拟实现死亡之Ping(Ping of death)
  6. MariaDB Galera Cluster 部署(如何快速部署MariaDB集群)
  7. 自己动手实现简单的Vector
  8. 编写程序,从vector&lt;char&gt;初始化string
  9. Puppeteer学习之小试牛刀
  10. smbclient匿名访问win7共享文件夹
  11. RNN入门(一)识别MNIST数据集
  12. 【数学建模】day04-插值与拟合
  13. DNSCrypt
  14. 第28月第21天 记事本Unicode 游戏编程中的人工智能技术
  15. Confluence 6 用户宏示例 - Color and Size
  16. 【BZOJ1856】[SCOI2010]字符串(组合数学)
  17. js 对象的_proto_属性 和函数的prototype属性分析
  18. SP2713 GSS4
  19. 题目1040:Prime Number(第k个素数)
  20. hdu多校(二) 1004 1007 1010

热门文章

  1. POJ2976(最大化平均值)
  2. [转载]Ubuntu下ssh服务的安装与登陆(ssh远程登陆)
  3. java中内部类的讲解
  4. 数据库:sql 多表联合更新【转】
  5. 执行: python manage.py makemigrations报AttributeError: &#39;str&#39; object has no attribute &#39;decode&#39;
  6. 简单的windows作业管理(自己也没弄透彻)
  7. java反射专题二
  8. C语言获取系统时间
  9. PROCEDURE存储过程传入表参数
  10. cocos2d-js动作模块使用(自用,只有代码)