Codeforces 864E - Fire(dp)

原题连接：http://codeforces.com/problemset/problem/864/E

题意：一个人想从大火中带走一些东西。每次他只能带一个，耗时t_i ,价值为p_i, 当总时间超过d_i时不能被带走。问他如何按顺序带走物品使价值总和最大。

思路：背包问题。分为取和不取两种情况1.dp[i][j]=max(dp[i-1][j], dp[i-1][j-t]+p), j<d;

　　　　　　　　　　　　　　　　　　2.dp[i][j]=max(dp[i-1][j], dp[i][j]);

AC代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 using namespace std;

 struct G{

     int t,d,v;

     int id;

 }g[];

 int dp[][];

 bool vis[][];

 bool cmp(G a, G b){

     return a.d<b.d;

 }

 int main()

 {

     int n,maxx=;

     scanf("%d", &n);

     memset(dp, , sizeof(dp));

     memset(vis, , sizeof(vis));

     for(int i=;i<=n;i++){

         scanf("%d %d %d", &g[i].t, &g[i].d, &g[i].v);

         g[i].id=i;

         maxx=max(maxx, g[i].d);

     }

     sort(g+, g+n+, cmp);

     int b;

     for(int i=;i<=n;i++){

         b=;

         for(int j=;j<=maxx;j++){

             if(j>=g[i].t&&j<g[i].d&&dp[i-][j]<dp[i-][j-g[i].t]+g[i].v){

                 dp[i][j]=dp[i-][j-g[i].t]+g[i].v;

                 vis[i][j]=;

             }

             else dp[i][j]=dp[i-][j];

             if(dp[i][j]>=dp[i][b]) b=j;

         }

     }

     printf("%d\n", dp[n][b]);

     vector<int> ans;

     for(int i=n;i;i--){//反推，得到最优取法

         if(vis[i][b]){

             ans.push_back(g[i].id);

             b-=g[i].t;

         }

     }

     printf("%d\n", ans.size());

     for(int i=ans.size()-;i>=;i--) printf("%d ",ans[i]);

     return ;

 }

巴特西

Codeforces 864E - Fire(dp)

最新文章

热门文章