【题解】城堡

解法一：动态规划DP

我们容易想到小贪心，如果要驻守第 i i i 个城堡，应选择最后那个与 i i i 有路径的城堡。反证：如果有两条路 u 1 → v , u 2 → v ( u 2 > u 1 ) u_1→v,u_2→v(u_2>u_1) u1​→v,u2​→v(u2​>u1​)，我们选择在攻打完成 u 1 u_1 u1​ 城堡时就驻守 v v v，和在 u 2 u_2 u2​ 的价值没区别，而且这样做可能导致在攻打 u 1 + 1... u 2 u_1+1...u_2 u1​+1...u2​ 的城堡时出现士兵不足的现象。

设 p [ i ] p[i] p[i] 为最后一个与 i i i 相连的城堡编号。对于每条路径 u , v u,v u,v，更新 p [ v ] = m a x { u } p[v]=max{u} p[v]=max{u}，这样一来就不用考虑判重的情况了。

设 f [ i ] [ j ] f[i][j] f[i][j] 为在攻打完前 i i i 个城堡后，还有 j j j 个士兵时，驻守城堡的最大值。

考虑如何转移。如果要攻打 i i i，显然前提条件为士兵数大于等于 a [ i ] a[i] a[i]。由于第 i i i 个城堡攻打完后，可以派士兵去驻守一些城堡 v 1 , v 2 , v 3 , . . . , v s ( k ∈ [ 1 , s ] , p [ v k ] = i ) v_1,v_2,v_3,...,v_s(k∈[1,s],p[v_k]=i) v1​,v2​,v3​,...,vs​(k∈[1,s],p[vk​]=i)。最直接的方法，枚举 k = 0... s k=0...s k=0...s，表示驻守 k k k 个城堡，定义 d [ k ] d[k] d[k] 为驻守 k k k 个城堡的最大值，那么方程为：

f [ i ] [ j ] = m a x { f [ i − 1 ] [ j + k − b [ i ] ] + d [ k ] } f[i][j]=max{f[i-1][j+k-b[i]]+d[k]} f[i][j]=max{f[i−1][j+k−b[i]]+d[k]}

如何算 d [ k ] d[k] d[k] 呢？我们对 v 1 , v 2 , . . . , v s v_1,v_2,...,v_s v1​,v2​,...,vs​ 按驻守价值 C C C 排序，对其求一遍前缀和，就是 d [ 1... s ] d[1...s] d[1...s]。特别的， d [ 0 ] = 0 d[0]=0 d[0]=0。

时间：我们枚举了 i , j , k i,j,k i,j,k，时间相当于枚举 i , k , j i,k,j i,k,j，由于对于 k k k，每个 i i i 的 k k k 的总和等于 n n n，即枚举 i , k i,k i,k 的时间相当于枚举 1... n 1...n 1...n 的时间。因此时间复杂度为 O ( n ( k + ∑ i = 1 n b [ i ] ) ) O(n(k+sum_{i=1}^{n}b[i])) O(n(k+∑i=1n​b[i])) 。

#include
using namespace std;
int n,m,k,f[5010][5010],S,u,v,p[5010],d[5010],ans=-0x3f3f3f3f;
int a[5010],b[5010],c[5010];
vectorvec[5010];
bool cmp(int x,int y)
{
	return c[x]>c[y];
}
int main()
{
	freopen("castle.in","r",stdin);
	freopen("castle.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		p[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		p[v]=max(p[v],u);
	}
	for(int i=1;i<=n;i++)
	{
		vec[p[i]].push_back(i); //压 vector，方便统计 i 时，p[j]=i 的 j
	}
	memset(f,0x80,sizeof f);
	f[0][k]=0;
	for(int i=1;i<=n;i++)
	{
		sort(vec[i].begin(),vec[i].end(),cmp);
		for(int j=0;j
			d[j+1]=d[j]+c[vec[i][j]];
		}
		for(int j=0;j<=5000;j++)
		{
			for(int k=0;k<=vec[i].size();k++)
			{
				if(j+k-b[i]<=5000&&j+k-b[i]>=a[i])f[i][j]=max(f[i][j],f[i-1][j+k-b[i]]+d[k]);
			}
			if(i==n)
			{
				ans=max(ans,f[i][j]);
			}
		}
	}
	if(ans>=0)printf("%d",ans);
	else printf("-1");
	return 0;
}

解法二：贪心（+优先队列）

如果我们每攻打一个城堡 i i i，就立刻驻守第 v e c [ i ] [ 0... s − 1 ] vec[i][0...s-1] vec[i][0...s−1] 个城堡，显然不是最优策略。

为什么呢？当我们在以后攻打城堡 i ′ i' i′ 时，发现士兵不够，什么原因？是因为在之前，每攻打完一个城堡就驻守士兵，导致士兵数量过少。这时，我们可以“反悔”，也就是撤销对一个城堡的驻守，增多士兵人数。撤销时要在原来我们驻守的城堡 j 1 , j 2 , j 3 , . . . , j m j_1,j_2,j_3,...,j_m j1​,j2​,j3​,...,jm​ 这 m m m 个城堡中选择价值最小的第 j j j 个城堡，把驻守在那里的士兵调回来，找最小可以用优先队列完成，时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

这种贪心称为反悔型贪心，是常用的一种贪心策略。