（区间 dp）洛谷 P6879 JOI2020 Collecting Stamps 3 题解

题意

给定一个周长为 $L$ 的圆，从一个点出发，有 $N$ 个黑白熊雕像，编号为 $1$ 到 $N$，第 $i$ 个雕像在顺时针 $X_i$ 米处，如果你没有在 $T_i$ 秒内收集到这个黑白熊雕像，那么这个雕像就会发出“唔噗噗噗”的声音然后爆炸。

现在 JOI 君在这个点，他每秒可以移动 $1$ 米，顺时针或者逆时针的移动都是允许的。

JOI 君想问，他最多能收集到多少个黑白熊雕像？

$1\le N\le 200$，$2\le L\le 10^9$，$1\le X_i<L$，$X_i<X_{i+1}$，$0\le T_i\le 10^9$。

思路

首当其冲破环成链。

发现可以顺时针或逆时针走，即可以停在区间的左或者右去收集雕塑。在洛谷 P1220 关路灯中同样是这样的套路，所以考虑朴素地设 $f_{i,j,op}$ 表示收集区间在 $[i,j]$ 的雕塑，收集完之后要停在左或右端点，可以收集到最大雕塑数量。

但是这一题还有一个时间限制，要在特定的时间点之前（包括这个时间点）收集到特定的雕塑，不一定能将区间 $[i,j]$ 的雕塑全部收集完。因此我们改变一下状态，是贡献与时间挂钩：设 $f_{i,j,k,op}$ 表示收集区间 $[i,j]$ 的雕塑，收集了 $k$ 个，收集完之后停在左或右端点，花费的最小时间。

因为在起点也可以顺时针和逆时针走，所以我们设破环成链之后的 $n+1$ 号点为起点，左圈逆时针为 $n\sim 1$，右圈顺时针为 $n+2\sim 2n+1$。

初始化 $x_{n+1}=L,t_{n+1}=0$，$f$ 极大值。

从一开始在起点（收集 $k=0$ 个雕塑时），就得先从起点走过去包含了 $n+1$ 的、期望的区间 $[i,j]$ 的左或右端点了（$i,j$ 分别在起点 $n+1$ 的左端右端，即 $i\in [1,n+1],j\in [n+1,2n+1]$）：
$$\begin{array}{c}{f}_{i,j,0,0}=L-a_i\\ f_{i,j,0,1}=a_j-L\end{array}$$

其实接下来和关路灯这道题大差不差了。不过这题多了分别考虑不取或者取雕塑。

不取的话直接从雕塑数为 $k$ 的状态转移过来：
f i , j , k , 0 = min ⁡ { f i + 1 , j , k , 0 + ∣ x i + 1 − x i ∣ , f i + 1 , j , k , 1 + ∣ x j − x i ∣ } f i , j , k , 1 = min ⁡ { f i , j − 1 , k , 0 + ∣ x i − x j ∣ , f i , j − 1 , k , 1 + ∣ x j − 1 − x j ∣ } \begin{matrix} f_{i,j,k,0}=\min\{f_{i+1,j,k,0}+|x_{i+1}-x_i|,f_{i+1,j,k,1}+|x_j-x_i|\}\\ f_{i,j,k,1}=\min\{f_{i,j-1,k,0}+|x_i-x_j|,f_{i,j-1,k,1}+|x_{j-1}-x_j|\} \end{matrix} fi,j,k,0​=min{fi+1,j,k,0​+∣xi+1​−xi​∣,fi+1,j,k,1​+∣xj​−xi​∣}fi,j,k,1​=min{fi,j−1,k,0​+∣xi​−xj​∣,fi,j−1,k,1​+∣xj−1​−xj​∣}​

取的话就从雕塑数为 $k-1$ 的状态转移过来，不过要注意小于要求的时间节点：

• f i , j , k , 0 = min ⁡ { f i + 1 , j , k − 1 , 0 + ∣ x i + 1 − x i ∣ , f i + 1 , j , k − 1 , 1 + ∣ x j − x i ∣ } f_{i,j,k,0}=\min\{f_{i+1,j,k-1,0}+|x_{i+1}-x_i|,f_{i+1,j,k-1,1}+|x_j-x_i|\} fi,j,k,0​=min{fi+1,j,k−1,0​+∣xi+1​−xi​∣,fi+1,j,k−1,1​+∣xj​−xi​∣}
  可以转移当且仅当 min ⁡ { } \min\{\} min{} 内的项不大于 $t_i$，即取在 $i$ 上的雕塑；
• f i , j , k , 1 = min ⁡ { f i , j − 1 , k − 1 , 0 + ∣ x i − x j ∣ , f i , j − 1 , k − 1 , 1 + ∣ x j − 1 − x j ∣ } f_{i,j,k,1}=\min\{f_{i,j-1,k-1,0}+|x_i-x_j|,f_{i,j-1,k-1,1}+|x_{j-1}-x_j|\} fi,j,k,1​=min{fi,j−1,k−1,0​+∣xi​−xj​∣,fi,j−1,k−1,1​+∣xj−1​−xj​∣}
  可以转移当且仅当 min ⁡ { } \min\{\} min{} 内的项不大于 $t_j$，即取在 $j$ 上的雕塑。

然后统计答案，找到 $k$ 最大的合法状态即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=402,inf=0x3f3f3f3f;
ll n,L,x[N],t[N];
ll f[N][N][N][2];
int main()
{scanf("%lld%lld",&n,&L);for(int i=1;i<=n;i++){scanf("%lld",&x[i]);x[i+n+1]=x[i]+L;}x[0]=0,x[n+1]=L;for(int i=1;i<=n;i++){scanf("%lld",&t[i]);t[i+n+1]=t[i];}memset(f,inf,sizeof(f));//起点是n+1 for(int j=n+1;j<=n+1+n;j++)//右 {for(int i=n+1;j<=i+n;i--)//左 {f[i][j][0][0]=L-x[i];//起点 向左 f[i][j][0][1]=x[j]-L;//起点 向右 }}for(int len=2;len<=n+1;len++)//成环 {for(int i=1;i<=n+1;i++)//左端点 {ll j=i+len-1;for(int k=1;k<len;k++){f[i][j][k][0]=min(f[i][j][k][0],min(f[i+1][j][k][0]+abs(x[i+1]-x[i]),f[i+1][j][k][1]+abs(x[j]-x[i])));f[i][j][k][1]=min(f[i][j][k][1],min(f[i][j-1][k][0]+abs(x[i]-x[j]),f[i][j-1][k][1]+abs(x[j-1]-x[j])));if(f[i+1][j][k-1][0]+abs(x[i+1]-x[i])<=t[i])//取i，i+1->i f[i][j][k][0]=min(f[i][j][k][0],f[i+1][j][k-1][0]+abs(x[i+1]-x[i]));if(f[i+1][j][k-1][1]+abs(x[j]-x[i])<=t[i])//取i，j->i f[i][j][k][0]=min(f[i][j][k][0],f[i+1][j][k-1][1]+abs(x[j]-x[i]));if(f[i][j-1][k-1][0]+abs(x[i]-x[j])<=t[j])//取j，i->jf[i][j][k][1]=min(f[i][j][k][1],f[i][j-1][k-1][0]+abs(x[i]-x[j]));if(f[i][j-1][k-1][1]+abs(x[j-1]-x[j])<=t[j])//取j，j-1->jf[i][j][k][1]=min(f[i][j][k][1],f[i][j-1][k-1][1]+abs(x[j-1]-x[j])); }}}ll ans=0;for(int len=2;len<=n+1;len++){for(int i=1;i<=n+1;i++){ll j=i+len-1;for(ll k=len;k>=1;k--){if(ans>=k)break;if(f[i][j][k][0]<inf||f[i][j][k][1]<inf){ans=max(ans,k);break;}}}}printf("%lld",ans);return 0;
}