分析

不难发现，对于一个城堡，早驻守不如晚驻守。因为驻守早了完全没有额外收益，驻守晚了也没有额外代价。所以对于每个城堡 \(x\)，记录 \(d(x)\) 为 \(x\) 的最晚可控制时间。也就是它必须在哪一个城堡被攻下之前，必须派兵驻守。特别的，如果某个城堡是独立的，令这个时间为它自身的编号。

设 \(f(i,j)\) 为已经攻下了前 \(i\) 个城堡，攻打第 \(i\) 个城堡之后还剩下 \(j\) 个人，所能获得的最大收益。对于 \(i=0\) 的所有状态，它们的初始值为 0，其余为负无穷。

设 \(A=\max_{i=1}^n{ \{ a_i\} }\)，\(B=\max_{i=1}^n{\{ b_i \}}\)。

对于攻打城堡，就像背包问题一样 \[ f(i,j+b_i) = \max_{j \in [a_i,A+B]}{\{ f(i-1,j) \}} \] 对于派兵驻守，则是要贪心地按照 \(d(x)\) 递增的顺序来求解。排序后，已经驻守过的城堡不需要再次驻守，所以维护一个指针 \(pos\)，每驻守一个，\(pos+1\)，驻守的时间 \(x\) 的时间必须是 \(d(x)\)。转移也是很简单的 \[ f(i,j) = \max_{j \in [0,A+B-1]}{\{ f(i,j+1) + c_{pos} \}} \] 答案就是 \(\max_{i \in [0,A+B]}{\{ f(n,i) \}}\)。

大佬们都说这题比较简单，可是蒟蒻我感觉并不那么容易。首先虽然容易想到是以「占领的城堡数」和「人数」为状态的内容，但是由于它涉及 2 种转移，边界处理和转移顺序较为麻烦，所以使用了填表法和刷表法混用的方式。

第一种转移应当先于第二种转移，因为前者完成之后，后者以来的状态已经计算完毕。尽管第二种转移实质上也是 0/1 背包（每个城堡占领不占领），但是 \(j\) 依赖 \(j+1\) 的状态，所以倒序循环是错的，只能通过用另一种转移来计算。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5005;
int n, m, k, a[N], b[N], c[N], d[N];
ll f[N][N];
pair<int,int> p[N];
int read() {
    int a=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a;
}
int main() {
    int B=0;
    n=read(), m=read(), k=read();
    for(int i=1;i<=n;++i) {
        a[i]=read(), b[i]=read(), c[i]=read();
        d[i]=i;
        B+=b[i];
    }
    for(int i=1;i<=m;++i) {
        int x=read(), y=read();
        d[y]=max(d[y],x);
    }
    for(int i=1;i<=n;++i) p[i]=make_pair(d[i],c[i]);
    sort(p+1,p+n+1);
    memset(f,-0x7f,sizeof(f));
    for(int i=0;i<=k;++i) f[0][i]=0;
    int pos=1;
    for(int i=1;i<=n;++i) {
        for(int j=a[i];j<=k+B;++j)
            if(j+b[i]<=k+B) f[i][j+b[i]]=max(f[i][j+b[i]],f[i-1][j]);
        while(pos<=n&&p[pos].first==i) {
            for(int j=0;j<k+B;++j) f[i][j]=max(f[i][j],f[i][j+1]+p[pos].second);
            ++pos;
        }
    }
    long long ans=-1;
    for(int i=0;i<=k+B;++i) ans=max(ans,f[n][i]);
    printf("%lld\n",ans);
}