思路分析

看到每一道菜有选和不选两种决策，我们想到了01背包。但是，和普通的01背包相比有个区别，就是做每一个决策是具有后效性的：选了i道菜会影响i+k道菜的价值，也就是说，菜的价值会和选的顺序有关。因此，我们需要利用一个贪心确定一个选择的顺序，令按照这一顺序选择答案最优。通过证明我们可以得到可以按照的要求顺序排序。
证明：设目前的时间为t，则，若顺序最优，则符合：
化简后就能得到我们上面的结论。
接下来就是普通的01背包了。这里还需要处理一个问题：因为结果可能是负数，我们需要将dp数组全部初始化为负无穷，然后将dp[0]设为0后再开始状态转移。这是需要学习的处理方式。

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <climits>
using namespace std;
typedef long long ll;
const int maxn=60;
const int maxn2=1e6+10;
ll n,m,t;
struct ve{
    ll a,b,c;
};
vector<ve> de;
ll bi[maxn];
ll dp[maxn2];
ll lt[maxn2];
bool cmp(ve a1,ve a2){
    return a2.b*a1.c<a1.b*a2.c;
}
void pr(){
    for(int i=0;i<de.size();i++){
        ve pos=de[i];
        cout<<pos.a<<" "<<pos.b<<" "<<pos.c<<endl;
    }
}

int main()
{
    for(register int i=0;i<maxn2;i++) dp[i]=-INT_MAX;
    scanf("%lld %lld %lld",&n,&m,&t);
    for(int i=1;i<=n;i++){
        scanf("%lld",bi+i);
    }
    for(int i=1;i<=m;i++){
        ll j,aa,cc;
        scanf("%lld %lld %lld",&j,&aa,&cc);
        ve tmp;
        tmp.a=aa;
        tmp.c=cc;
        tmp.b=bi[j];
        de.push_back(tmp);
    }
    sort(de.begin(),de.end(),cmp);
    dp[0]=0;
//  pr();
    for(register int i=0;i<de.size();++i){
        ve pos=de[i];
        for(register int j=t;j>=pos.c;j--){
            dp[j]=max(dp[j],dp[j-pos.c]+pos.a-pos.b*j);
        }
    }
    ll ans=dp[1];
    for(int i=2;i<=t;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}