[JOI]2020 Final Problem.C

Xiphi · 2024-01-22 21:49:35 · 题解

参考了官方题解。

考虑 dp，设状态 dp_{S,i,t} 表示所盖的邮票集合为 S，当前所在的为 i，印张数为 t 的最短经过时间。这样状态就有 O(2^n \times n^2) 个然后转移是 O(n) 的。

考虑优化前面 dp_{S,i} 的部分。发现要盖的区域总是连续的，故设状态 dp_{l,r,t,op} 表示左端为第 i 个盖章处，右端为第 j 个盖章处，按下了 t 个印章的最短时间，op 表示现在位于左端还是右端，op=0 表示在左边，op=1 则表示在右边，状态数在 O(n^3) 左右。

接下来考虑转移方程，过程中设 dis(i,j) 表示两点距离，op 表示能不能取到：

• 若走到左边，继续往左走，则到达时间为 dp_{l,r,k,0}+X_{n-l+1}-X_{n-l}。转移方程就是：dp_{l+1,r,k+op,0}\gets dp_{l,r,k,0}+X_{n-l+1}-X_{n-l}（和之前的要取 \min）。

• 若走到左边，继续往右走，则到达时间为 dp_{l,r,k,0}+L-X_{n-l+1}+X_{r+1}。转移方程就是 dp_{l,r+1,k+op,1} \gets dp_{l,r,k,0}+L-X_{n-l+1}+X_{r+1} （和之前的要取 \min）。

• 若走到右边，继续往右走，则到达时间为 dp_{l,r,k,1}+X_{r+1}-X_{r}。转移方程是 dp_{l,r+1,k+op,1} \gets dp_{l,r,k,1}+X_{r+1}-X_{r}。

• 若走到右边，继续往左走，则到达时间为 dp_{l,r,k,1}+X_{r}+L-X_{n-l}。转移方程是 dp_{l+1,r,k+op,0} \gets dp_{l,r,k,1}+X_{r}+L-X_{n-l}。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,L,ans,t[205],x[205],dp[205][205][205][2];
signed main(){
//  freopen("test.in","r",stdin);
//  freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>L;
    for(int i=1;i<=n;++i){
        cin>>x[i];
    }
    x[n+1]=L;
    for(int i=1;i<=n;++i) cin>>t[i];
    memset(dp,0x3f,sizeof dp);
    dp[0][0][0][0]=0;
    dp[0][0][0][1]=0;
    for(int l=0;l<=n;++l){
        for(int r=0;r<=n;++r){
            if(n<=l+r) break;
            for(int k=0;k<=n;++k){
                int op =dp[l][r][k][0],
                    op1=dp[l][r][k][1];
                if(op<=1e12){
                    int esp1=x[n-l+1]-x[n-l],
                        esp2=L-x[n-l+1]+x[r+1];
                    int Op0=(op+esp1<=t[n-l]);
                    int Op1=(op+esp2<=t[r+1]);
                    dp[l+1][r  ][k+Op0][0]=min(dp[l+1][r  ][k+Op0][0],op+esp1);
                    dp[l  ][r+1][k+Op1][1]=min(dp[l  ][r+1][k+Op1][1],op+esp2);
                }
                if(op1<=1e12){
                    int esp1=L-x[n-l]+x[r],
                        esp2=x[r+1]-x[r];
                    int Op0=(op1+esp1<=t[n-l]);
                    int Op1=(op1+esp2<=t[r+1]);
                    dp[l+1][r  ][k+Op0][0]=min(dp[l+1][r  ][k+Op0][0],op1+esp1);
                    dp[l  ][r+1][k+Op1][1]=min(dp[l  ][r+1][k+Op1][1],op1+esp2);
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=n;++i)
    for(int j=0;j<=n;++j)
    for(int k=0;k<=n;++k){
        if(min(dp[i][j][k][0],dp[i][j][k][1])<=1e15){
            ans=max(ans,k);
        }
    }
    cout<<ans;
    return 0;
}