ZOJ Problem Set - 3211 Dream City
Chieh
posted @ 2014年12月27日 21:36
in ZOJ
, 319 阅读
题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3374
题意就是说有n棵树,每棵树有个初始值a个金币,而且每过一天会增加b个金币,求m天最多可以得到金币,而且必须每天都要砍一棵树
刚开始以为是贪心。。。Wa,后来举了个反例才发现自己的贪心是错的。。。那么应该怎么做这道题呢??DP。。。除了贪心我只能想到DP,该怎么DP呢。。。后来想到来个数组dp[i][j]表示前i棵树在j天最大可以产生多少。。。但是有个特别的值。。就是b。。。好像又把我卡住了。。。想一下,就是怎么来确定顺序呢。。。根据b排序。。。把b最小的放前面。。。这样到后面的时候,b已经是最优的了。。。所以这道题的大致感觉就是。当前要放那个哪个地方的话。。。前面的得先放好而且是最优的
ai[i][j]=max(ai[i-1][j],ai[i-1][j-1]+JLJ[i].b*(j-1)+JLJ[i].a);
这样答案就出来了
/* Author:Chieh Grow up happy */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <stack> #include <vector> #define LL long long using namespace std; const int maxn=250+10; struct he { int a,b; } JLJ[maxn]; int ai[maxn][maxn]; int n,m; int T; bool cmp(he a,he b) { return a.b<b.b; } void init() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) { scanf("%d",&JLJ[i].a); } for(int i=1; i<=n; i++) { scanf("%d",&JLJ[i].b); } } void play() { sort(JLJ+1,JLJ+1+n,cmp); memset(ai,0,sizeof(ai)); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(j<=i) ai[i][j]=max(ai[i-1][j],ai[i-1][j-1]+JLJ[i].b*(j-1)+JLJ[i].a); else break; } } printf("%d\n",ai[n][m]); } int main() { scanf("%d",&T); while(T--) { init(); play(); } //cout << "Hello world!" << endl; return 0; }