P6715 [CCO2018] Fun Palace 题解

执着之幻 · 2024-01-29 22:08:52 · 题解

原题链接

题目大意：

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

题目分析：

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

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

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

再看到这道题的数据范围，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) )