经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
洛谷P1107 & BZOJ1270 [BJWC2008]雷涛的小猫
来源:cnblogs  作者:oh_yes  时间:2018/12/3 10:13:41  对本文有异议

 

一道DP。

给你一个矩阵里面有很多数,你需要从上往下找到一种跳跃方法使得经过的点的价值之和最大。

具体题面见链接

 

洛谷P1107

BZOJ1270

很明显是一个二维的DP。

 

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int N, H, Delta;
  4. int t[2020][2020];//t为原始生成的图,同时也作为保存状态的二维数组
  5. int dp[2020];//dp[i]表示高度为i时取得的最大价值
  6. inline void input(){//输入数据并存为图,存图方式如上图图片
  7. scanf("%d%d%d", &N, &H, &Delta);
  8. for(register int i = 1; i <= N; i ++){
  9. int num;
  10. scanf("%d", &num);
  11. for(register int j = 1; j <= num; j ++){
  12. int temp;
  13. scanf("%d", &temp);
  14. t[temp][i]++;
  15. }
  16. }
  17. }
  18. int main(){
  19. input();
  20. for(register int i = 1; i <= H; i ++){
  21. for(register int j = 1; j <= N; j ++){
  22. if(i <= Delta){//当高度比Delta小时,当前状态只能从同一列的上一个状态转移
  23. t[i][j] += t[i - 1][j];//
  24. dp[i] = max(dp[i], t[i][j]);//当前高度能取得的最大价值为当前行所有状态的最大值
  25. continue;
  26. }
  27. t[i][j] += max(dp[i - Delta], t[i - 1][j]);//普通的状态转移方程
  28. dp[i] = max(dp[i], t[i][j]);//同时要更新当前高度能取得的最大价值
  29. }
  30. }
  31. printf("%d\n", dp[H]);
  32. return 0;
  33. }

 混搭码风,求谅解。

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号