ZOJ - 3211 Dream City (贪心+dp)

淡淡的烟草味﹌ 2022-05-27 14:14 286阅读 0赞

思路：增长速度快的只有放在后面砍才能获得最大的收益。

dp[i][j]表示从前i棵树中选出j棵树， 在前j天砍，砍得顺序就是排序的顺序

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int INF=0x3f3f3f3f;
  4. int T;
  5. int n, m;
  6. int dp[300][300];
  7. pair<int,int> p[300];
  9. void init(){
  10.     memset(dp, 0, sizeof(dp));
  11. }
  13. int main(){
  14.     scanf("%d", &T);
  15.     while(T--){
  16.         init();
  17.         scanf("%d%d", &n, &m);
  18.         for(int i=1; i<=n; i++)
  19.             scanf("%d", &p[i].second);
  20.         for(int i=1; i<=n; i++)
  21.             scanf("%d", &p[i].first);
  23.         sort(p+1, p+1+n);
  25.         for(int i=1; i<=n; i++)
  26.         {
  27.             for(int j=1; j<=m; j++)
  28.             {
  29.                 dp[i][j]=max(dp[i-1][j], dp[i-1][j-1]+p[i].first*(j-1)+p[i].second);//表示（前i-1棵树取j棵） 和（前i-1棵树取j-1棵与第j棵树的和）二者之间的最大值
  30.             }
  31.         }
  33.         for(int i=1; i<=n; i++)
  34.         {
  35.             for(int j=1; j<=m; j++)
  36.                 printf("%d ", dp[i][j]);
  37.             puts("");
  38.         }
  40.         printf("%d\n", dp[n][m]);
  41.     }
  44.     return 0;
  45. }

发表评论

表情：
评论列表 （有 0 条评论，286人围观）

还没有评论，来说两句吧...

相关阅读

    相关 ZOJ 3537 区间dp

    题意：给出一些点表示多边形蛋糕的定点的位置（如果蛋糕是凹多边形就不能切），切蛋糕时每次只能在顶点和顶点间切，每一次切蛋糕都有相应的代价，给出代价的公式，问把蛋糕切成多个三角形的

    蔚落蔚落/ 0 赞/ 273 阅读