题解：P12789 [ICPC 2024 Yokohama R] Peculiar Protocol

New_Void · 2026-05-18 22:33:15 · 题解

P12789 [ICPC 2024 Yokohama R] Peculiar Protocol

模拟赛的题，并没有切出。

思路

很显然是区间 DP，问题是如何转移。

考虑这个题有一个删掉一段区间剩下的数拼接起来的问题，所以并不好直接做，我们先考虑子问题：

• 假定区间 [l,r] 是可以进行若干次删除后被完全删除的，那么设进行了 x 次删除子区间操作，则贡献为 \frac{\sum_{i=l}^{r} a_i-xr}{d}，要求 \sum_{i=l}^{r} a_i-xr 能被 d 整除。容易发现若我们进行的删除操作次数 x 越小，且整个区间依然可以被完全删除，那么贡献定然更大，所以我们目的是处理出最小的删除操作 x 次，使得区间 [l,r] 能被完全删除。
• 发现处理出最小的 x 次操作并不好做，注意到 x 次操作定然会处理 x+1 段，所以不妨转化为将区间 [l,r] 分割成最多的段使得能被完全删除。

转化成这个就好做了，设 mx_{l,r} 表示区间 [l,r] 能被完全删除情况下能被分割成的最大段数，且每一段都能被完全删除，那么直接区间 DP，枚举端点 k，则有 mx_{l,r} = \max\left( mx_{l,r},\; \max_{l \le k < r} \bigl( mx_{l,k} + mx_{k+1,r} \bigr) \right)。

当转移后我们还需要再钦定一遍整个区间，看是否可以分割成前面 x 段，剩余一段且能被完全删除的情况，转移就是 mx_{l,r}= \max\left( mx_{l,r},x+1 \right)

处理完这个我们就可以直接依照这个做 dp 了，设 dp_{l,r} 表示区间 [l,r] 中能获得的最大可能总和，则转移跟 mx 数组同理。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&(-x))
#define ls (u<<1)
#define rs (u<<1|1)
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') k=k*10+c-'0',c=getchar();
    return k*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
const int N=505+10;
int a[N],dp[N][N],mx[N][N],sum[N];
inline int S(int r,int l){return sum[r]-sum[l-1];}
void solve(){
    int n=read(),d=read(),R=read();
    for (int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i];
    for (int len=1;len<=n;len++){
        for (int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            for (int k=l;k<r;k++){
                dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]);
                mx[l][r]=max(mx[l][r],mx[l][k]+mx[k+1][r]);
            }
            int p=mx[l][r];
            for (int x=0;x<=p;x++){
                // S-xr-cnt*d=S_rem
                // (S_rem-r) mod d=0
                // (S-xr-cnt*d-r) mod d=0
                // (S-xr-r) mod d=0
                // (S-(x+1)r) mod d=0
                if ((S(r,l)-(x+1)*R)%d==0 && S(r,l)>=(x+1)*R){
                    mx[l][r]=max(mx[l][r],x+1);
                    dp[l][r]=max(dp[l][r],(S(r,l)-(x+1)*R)/d);
                }
            }
        }
    }
    write(dp[1][n]);
}
signed main(){
    int T=1;
    while (T--) solve();
    return 0;
}