首页 > 代码库 > 入门动态规划 BZOJ 1270 雷涛的小猫
入门动态规划 BZOJ 1270 雷涛的小猫
1270: [BeijingWc2008]雷涛的小猫
Time Limit: 50 Sec Memory Limit: 162 MBSubmit: 1250 Solved: 643
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
Sample Output
8
HINT
这个题已经水得不能再水了,然而我还是WA了几次
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,h,d; 7 int mx[2010],a[2010][5010],dp[2010][5010]; 8 ///dp[i][j]第i颗树高度为j时可以获得的最大值 9 int ans; 10 int main(){ 11 scanf("%d%d%d",&n,&h,&d); 12 int x=0,y=0; 13 for(int i=1;i<=n;i++){ 14 scanf("%d", &x); 15 for(int j=1;j<=x;j++){ 16 scanf("%d",&y); 17 a[i][y]++;//不一定一个点只有一个 18 } 19 } 20 for(int i=h;i>=1;i--) 21 for(int j=1;j<=n;j++){ 22 dp[j][i]=max(dp[j][i+1],mx[i+d])+a[j][i]; 23 mx[i]=max(mx[i],dp[j][i]); 24 } 25 for(int i=h;i>=1;i--) 26 for(int j=1;j<=n;j++) ans=max(ans,dp[j][i]); 27 printf("%d\n", ans); 28 return 0; 29 }
入门动态规划 BZOJ 1270 雷涛的小猫
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。