CodeForces 864E Fire dp递推

CodeForces 864E

题意：有 n 个物品着火，每个物品要花 ti 时间扑灭，且在 >= di 时间后就会坏掉，物品价值为 pi 。 问最多可以救回多少价值，物品个数，及救哪些物品(要按抢救的顺序输出) 。

tags：

dp[i][j] 表示前 i 个物品花费了 j 时间最多可以救回多少价值。

先按 di 排序，转移即：

1】如不取第 i 个物品： dp[i][j] = max(dp[i][j], dp[i-1][j]) ；

2】 如取第 i 个物品： dp[i][j] = max(dp[i][j], dp[i-1][j-ti]+pi) 。 

类似于背包， O(100*2000) 。

当然，要打印救哪些物品，在转移的时候加个记录就 OK 了。

// 864E #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 105, M = 2005;struct Node {int t, d, p, id;bool friend operator < (Node a, Node b) {return a.d<b.d;} } item[N]; int n, pre[N][M], dp[N][M]; bool vis[N]; int main() {scanf("%d", &n);int mx = 0;rep(i,1,n){scanf("%d%d%d", &item[i].t, &item[i].d, &item[i].p);mx = max(mx, item[i].d);item[i].id = i;}sort(item+1, item+1+n);rep(i,1,n){rep(j,1,mx){if(dp[i][j] <= dp[i-1][j]){dp[i][j] = dp[i-1][j];pre[i][j] = j;}if(j-item[i].t>=0 && j<item[i].d)if(dp[i][j] <= dp[i-1][j-item[i].t]+item[i].p){dp[i][j] = dp[i-1][j-item[i].t]+item[i].p;pre[i][j] = j-item[i].t;}}}int ans1=-1, mj=-1;rep(j,1,mx)if(ans1<dp[n][j])ans1=dp[n][j], mj=j;printf("%d\n", ans1);int ans2=0;per(i,n,1){if(pre[i][mj]!=mj)++ans2, vis[i]=true;mj = pre[i][mj];}printf("%d\n", ans2);rep(i,1,n)if(vis[i])printf("%d ", item[i].id);return 0; }

转载于:https://www.cnblogs.com/sbfhy/p/7659080.html

总结

以上是生活随笔为你收集整理的CodeForces 864E Fire dp递推的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。