首页 > 代码库 > BZOJ 1270 Beijing Wc 2008 雷涛的小猫 动态规划
BZOJ 1270 Beijing Wc 2008 雷涛的小猫 动态规划
题目大意:给出一个棵果树,上面有些地方长了一些果子。现在有一只小猫想去吃这些果子,他从最高处往下跳,每到一个地方可以吧这个地方的果子全吃掉。也可以向旁边的果树上跳。问小猫最多能吃到多少果子。
思路:WC的无脑动规大水题。随便加个小优化就过了。。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 3510 using namespace std; #define max(a,b) ((a) > (b) ? (a):(b)) int cnt,h,detla; int src[MAX][MAX],f[MAX][MAX]; int _max[MAX]; int main() { cin >> cnt >> h >> detla; memset(_max,0xef,sizeof(_max)); for(int num,i = 1; i <= cnt; ++i) { scanf("%d",&num); for(int x,j = 1; j <= num; ++j) { scanf("%d",&x); ++src[i][x]; } } for(int i = 1; i <= cnt; ++i) f[i][h] = src[i][h]; for(int j = h - 1; ~j; --j) for(int i = 1; i <= cnt; ++i) { f[i][j] = max(f[i][j + 1],_max[j + detla]) + src[i][j]; _max[j] = max(_max[j],f[i][j]); } cout << _max[0] << endl; return 0; }
BZOJ 1270 Beijing Wc 2008 雷涛的小猫 动态规划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。