51nod1455(dp)
2024-08-31 21:48:13
题目链接: 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 ;
}
最新文章
- HDU5887 Herbs Gathering(2016青岛网络赛 搜索 剪枝)
- 广播后刷新界面-调用其他界面的方法触动广播后刷新该界面UI
- 在html 中嵌入优酷视频
- sqlserver 查询库中有多少张表
- 模拟实现死亡之Ping(Ping of death)
- MariaDB Galera Cluster 部署(如何快速部署MariaDB集群)
- 自己动手实现简单的Vector
- 编写程序,从vector<;char>;初始化string
- Puppeteer学习之小试牛刀
- smbclient匿名访问win7共享文件夹
- RNN入门(一)识别MNIST数据集
- 【数学建模】day04-插值与拟合
- DNSCrypt
- 第28月第21天 记事本Unicode 游戏编程中的人工智能技术
- Confluence 6 用户宏示例 - Color and Size
- 【BZOJ1856】[SCOI2010]字符串(组合数学)
- js 对象的_proto_属性 和函数的prototype属性分析
- SP2713 GSS4
- 题目1040:Prime Number(第k个素数)
- hdu多校(二) 1004 1007 1010
热门文章
- POJ2976(最大化平均值)
- [转载]Ubuntu下ssh服务的安装与登陆(ssh远程登陆)
- java中内部类的讲解
- 数据库:sql 多表联合更新【转】
- 执行: python manage.py makemigrations报AttributeError: &#39;str&#39; object has no attribute &#39;decode&#39;
- 简单的windows作业管理(自己也没弄透彻)
- java反射专题二
- C语言获取系统时间
- PROCEDURE存储过程传入表参数
- cocos2d-js动作模块使用(自用,只有代码)