洛谷P1107 & BZOJ1270 [BJWC2008]雷涛的…
2018-12-02 06:12:14来源:博客园 阅读 ()
一道DP。
给你一个矩阵里面有很多数,你需要从上往下找到一种跳跃方法使得经过的点的价值之和最大。
具体题面见链接
洛谷P1107
BZOJ1270
很明显是一个二维的DP。
#include<bits/stdc++.h> using namespace std; int N, H, Delta; int t[2020][2020];//t为原始生成的图,同时也作为保存状态的二维数组 int dp[2020];//dp[i]表示高度为i时取得的最大价值
inline void input(){//输入数据并存为图,存图方式如上图图片 scanf("%d%d%d", &N, &H, &Delta); for(register int i = 1; i <= N; i ++){ int num; scanf("%d", &num); for(register int j = 1; j <= num; j ++){ int temp; scanf("%d", &temp); t[temp][i]++; } } }
int main(){ input(); for(register int i = 1; i <= H; i ++){ for(register int j = 1; j <= N; j ++){ if(i <= Delta){//当高度比Delta小时,当前状态只能从同一列的上一个状态转移 t[i][j] += t[i - 1][j];// dp[i] = max(dp[i], t[i][j]);//当前高度能取得的最大价值为当前行所有状态的最大值 continue; } t[i][j] += max(dp[i - Delta], t[i - 1][j]);//普通的状态转移方程 dp[i] = max(dp[i], t[i][j]);//同时要更新当前高度能取得的最大价值 } } printf("%d\n", dp[H]); return 0; }
混搭码风,求谅解。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- Building & Debugging chromium on CLion for Linu 2020-05-19
- 洛谷P1164->小A点菜 2020-05-18
- 表达式·表达式树·表达式求值 2020-04-29
- STL之<string> 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash