自动搬运

查看原文

来自洛谷，原作者为

	执着之幻 愿我们都能有光明的前途！

搬运于2025-08-24 22:23:19，当前版本为作者最后更新于2024-01-29 22:08:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

题目大意：

给出两个整数 $n$ 和 $e$， 有一个含有 $n$ 个点的链 $(i , i+1)$，每条链都有两个数值 $a_i$ 和 $b_i$ 作为限制，如果其中有一个数超过对应的限制，那条链就会被打开，即链上的数可以发生变化，现在让你构造出一个数列，使得 $1$ 号点不能超过限制 $e$，求这个数列总和的最大值。

题目分析：

这是一道十分巧妙的 $dp$ 算法题。

首先我们不妨从只有一条链的情况开始分析：

记这条链上左边的数为 $x$，右边的数为 $y$，根据题目要求我们大致可以分成一下几种情况讨论。

• $x\le a_i, y\le b_i$，此时可以发现这两个数不能互相影响，即两数无关联

• $x+y\ge a_i+b_i$，此时可以发现这两个数都超过了原来的限制，这两个数无论如何变化，它总能保持这条链处于打开的状态，即相当于没有这条链

• $x+y < a_i+b_i$ 且 $x\ge a_i$，此时可以发现这条链是处于打开的状态，而如果要保持这条链是打开的状态，左边的数最多可以减少 $(x-a_i)$ ，右边的数最多可以增加 $(x-a_i)$ ，即最终左边的数最多可以为 $a_i$，右边的数最多可以为 $(y+x-a_i)$，才能保证这条边的状态是打开的

• $x+y < a_i+b_i$ 且 $y\ge b_i$，此时可以发现这条链也是处于打开的状态，而如果要保持这条链是打开的状态，右边的数最多可以减少 $(y-b_i)$ ，左边的数最多可以增加 $(y-b_i)$ ，即最终左边的数最多可以为 $(x+y-b_i)$，右边的数最多可以为 $b_i$，才能保证这条边的状态是打开的

再看到这道题的数据范围，$1\le N\le 10^3 ,1\le e,a_i,b_i\le 10^4$，可以推测这道题的时间复杂度为 $O(N\times \max(a_i+b_i) )$

接下来我们就考虑状态表示以及状态的转移

通过上面的分析，我们可以记一个状态 $f[i][j]$ ，表示在前 $i$ 位中，当前第 $i$ 位为 $j$ 的最大总和，则答案就是 $\max (f[n][1\dots \max (a_i+b_i)])$

最后考虑状态怎么转移：

从上面的分类讨论，我们可以直接对 $j$ 进行讨论：

• 若 $j\ge a_i+b_i$，说明此时左边的数为 $j$ 时，这条链是永远处于打开状态的，所以状态转移方程为： $f[i+1][j]=\max(f[i+1][j],f[i][j])$

• 若 $a_i\le j< a_i+b_i$，说明此时左边的数为 $j$ 时，这条链可以在左边达到 $a_i$ 的时候对右边的状态进行转移，所以状态转移方程为：$f[i+1][j-a[i]]=\max(f[i+1][j-a[i]],f[i][j])$

• 若 $b_i\le j< a_i+b_i$，说明此时左边的数为 $j$ 时，这条链可以保证在右边达到 $b_i$ 的时候对右边的状态进行转移，状态转移方程为：$f[i+1][j]=\max(f[i+1][j],f[i][j-b[i]]+b[i])$

• 若 $j< a_i$，说明此时左边的数为 $j$ 时，右边的数可以在没有达到 $b_i$ 的时候对右边的状态进行转移，状态转移方程为： $f[i+1][1\dots b_i]=\max(f[i+1][1\dots b_i],f[i][j]+j)$

可以发现，在状态转移的时候只有第三种情况和第四种情况对右边的数进行增加，而第一种和第二种只是直接对左边的数的顺接，但是可以通过证明发现，在前面或后面的转移中，一定会对第一种和第二种情况完成覆盖，所以不会出现漏情况的局面。

最终时间复杂度：$O(N\times \max(a_i+b_i) )$

$AC$ 代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1100],b[1100],f[1100][21000],k,ans;
int main()
{
	cin>>n>>k;m=k;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		m=max(m,a[i]+b[i]);
	}
	for(int i=0;i<k;i++)f[1][i]=i;
	for(int i=1;i<n;i++)
	{
		int ma=0;
		for(int j=0;j<m;j++)
		{
			if(j>=a[i]+b[i])f[i+1][j]=max(f[i+1][j],f[i][j]);
			else
			{
				if(j>=a[i])f[i+1][j-a[i]]=max(f[i+1][j-a[i]],f[i][j]);
				if(j>=b[i])f[i+1][j]=max(f[i+1][j],f[i][j-b[i]]+b[i]);
			}
			if(j<a[i])ma=max(ma,f[i][j]);
		}
		for(int j=0;j<b[i];j++)f[i+1][j]=max(f[i+1][j],ma+j);
	}
	for(int i=0;i<m;i++)ans=max(ans,f[n][i]);
	cout<<ans;
	return 0;
}