CodeForces - 864E （背包+路徑）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define N 123
int dp[N*20];
struct node
{
    int time,end,d;
    int x;
}a[N];
int cmp(node e,node f)
{
    return e.end<f.end;
}
vector<int>Q[2100];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d",&a[i].time,&a[i].end,&a[i].d);
        a[i].x=i+1;
    }
    sort(a,a+n,cmp);
    memset(dp,0,sizeof(dp));    int maxx=0,t=0;
    for(int i=0;i<n;i++)
    {
        for(int j=a[i].end-1;j>=a[i].time;j--)
        {
            if(dp[j-a[i].time]+a[i].d>dp[j])
            {
                Q[j].clear();///清空之前保留的
                int len=Q[j-a[i].time].size();
                for(int k=0;k<len;k++)///利用背包特性，將上一個背包所需的物品轉(zhuǎn)移
                    Q[j].push_back(Q[j-a[i].time][k]);
                Q[j].push_back(a[i].x);///加上此時要添加的物品
                dp[j]=dp[j-a[i].time]+a[i].d;///更新當(dāng)前背包
                if(maxx<dp[j])///保留最大值以及最大值所在的時間
                    maxx=dp[t=j];
            }
        }
    }
    printf("%d\n%d\n",maxx,Q[t].size());
    for(int i=0;i<Q[t].size();i++)
        printf("%d%c",Q[t][i],i==Q[t].size()-1?'\n':' ');
    return 0;
}