CodeForces 864E

題意：有 n 個物品著火，每個物品要花 ti 時間撲滅，且在 >= di 時間后就會壞掉，物品價值為 pi 。 問最多可以救回多少價值，物品個數(shù)，及救哪些物品(要按搶救的順序輸出) 。

tags：

dp[i][j] 表示前 i 個物品花費了 j 時間最多可以救回多少價值。

先按 di 排序，轉(zhuǎn)移即：

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) 。

當然，要打印救哪些物品，在轉(zhuǎn)移的時候加個記錄就 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; }

轉(zhuǎn)載于:https://www.cnblogs.com/sbfhy/p/7659080.html

總結(jié)

以上是生活随笔為你收集整理的CodeForces 864E Fire dp递推的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。