[Codeforces]864E. Fire

題目連結：http://codeforces.com/contest/864/problem/E

類似背包的dp，dp[i][j] = max(dp[i][j-1],dp[i-1][j],dp[i-1][j-item[i].t]+item[i].p)。
最後再遞迴找是從哪裡轉移過來的。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
typedef pair<int,int> Pair;
struct Ken{
    int t,d,p,id;
    bool operator<(const Ken &x)const{
        return d < x.d;
    }
}item[105];
int dp[105][2005],ans;
pair<int, Pair> f[105][2005];
vector<int> v;
void solve(int x,int y){
    if(f[x][y].F == 0)return;
    ans++;
    v.PB(f[x][y].F);
    solve(f[x][y].S.F,f[x][y].S.S);
}
int main(){jizz
    int n;cin >> n; 
    for(int i = 1 ; i <= n ; i++)cin >> item[i].t >> item[i].d >> item[i].p,item[i].id = i;
    sort(item+1,item+n+1);
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j < item[i].d; j++){
            dp[i][j] = dp[i-1][j];
            f[i][j] = f[i-1][j];
            if(j >= item[i].t && dp[i-1][j-item[i].t]+item[i].p> dp[i][j] && j < item[i].d){
                dp[i][j] = dp[i-1][j-item[i].t]+item[i].p;
                f[i][j] = {item[i].id,{i-1,j-item[i].t}};
            }if(dp[i][j-1] > dp[i][j]){
                dp[i][j] = dp[i][j-1];
                f[i][j] = f[i][j-1];
            }
        }
    }
    int tp = 0,y;
    cout << dp[n][item[n].d-1] <<endl;;
    solve(n,item[n].d-1);
    reverse(v.begin(),v.end());
    cout << ans << endl;
    for(int i:v)cout << i << ' ';
    return 0;
}