背包DP，決策的時候記一下 jc[i][j]=1 表示第i個物品容量為j的時候要選，輸出方案的時候倒推就好了

#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=2001; struct poi{int t,ddl,p,id;}a[maxn]; int n,top,ansi,cnt; int f[110][maxn],st[maxn],jc[110][maxn]; bool cmp(poi a,poi b){return a.ddl<b.ddl;} int main() {scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d%d%d",&a[i].t,&a[i].ddl,&a[i].p);a[i].id=i;}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){for(int j=0;j<a[i].t;j++)f[i][j]=f[i-1][j];for(int j=a[i].t;j<=a[i].ddl-1;j++){f[i][j]=f[i-1][j];if(f[i-1][j-a[i].t]+a[i].p>f[i][j]){f[i][j]=f[i-1][j-a[i].t]+a[i].p;jc[i][j]=1;}}}int ans=0;for(int i=0;i<a[n].ddl;i++)if(f[n][i]>ans)ans=f[n][i],ansi=i;for(int i=n;i&&ansi;i--)if(jc[i][ansi])cnt++,st[++top]=i,ansi-=a[i].t;printf("%d\n%d\n",ans,cnt);for(;top;top--)printf("%d ",a[st[top]].id); } View Code

?

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

總結(jié)

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

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