CF1271D Portals 题解
分析
不难发现,对于一个城堡,早驻守不如晚驻守。因为驻守早了完全没有额外收益,驻守晚了也没有额外代价。所以对于每个城堡 \(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);
}