首页 > 代码库 > 【bzoj1270】[BeijingWc2008]雷涛的小猫 dp
【bzoj1270】[BeijingWc2008]雷涛的小猫 dp
题目描述
输入
输出
样例输入
样例输出
8
题解
dp
设f[i][j]表示在第i棵树的j高度时最多吃到的柿子数。
那么只有两种可能能够到达这个位置：滑下来、跳下来。
滑下来直接用f[i][j+1]转移，跳下来需要在dp同时记录一个g数组，g[j]表示j高度时最多的柿子数，这样可以用g[j+D]转移。
然后跑dp即可。
#include <cstdio>#include <algorithm>#define N 2010using namespace std;int f[N][N] , num[N][N] , g[N];inline int read(){ int ret = 0; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) ch = getchar(); while(ch >= ‘0‘ && ch <= ‘9‘) ret = (ret << 3) + (ret << 1) + ch - ‘0‘ , ch = getchar(); return ret;}int main(){ int n , m , d , k , i , j; n = read() , m = read() , d = read(); for(i = 1 ; i <= n ; i ++ ) { k = read(); while(k -- ) num[i][read()] ++ ; } for(j = m ; ~j ; j -- ) { for(i = 1 ; i <= n ; i ++ ) { f[i][j] = f[i][j + 1] + num[i][j]; if(j + d <= m) f[i][j] = max(f[i][j] , g[j + d] + num[i][j]); g[j] = max(g[j] , f[i][j]); } } printf("%d\n" , g[0]); return 0;}
【bzoj1270】[BeijingWc2008]雷涛的小猫 dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。