P12789 [ICPC 2024 Yokohama R] Peculiar Protocol

· · 题解

存在一个显然的性质：对于任意一个区间 \left [ l,r \right ] ，设用其中元素至多能参加 x 场婚礼，那么对于任意 y \le x，都可以找到一种合法的方案。

所以我们可以统计每个区间能参加婚礼的最大次数，并借助这个判定一个区间能否完全利用。

转移是简易的，因为只关心最大次数，所以只需要枚举断点，判断剩下元素总和对 d 取模是否为 r 即可。

为了判定简便，可以事先预处理达到每个余数至少要举办几场婚礼。

其余细节可以见代码。

代码

#include<bits/stdc++.h>
using namespace std;
template <typename T>
void in(T &x){
    char c=getchar(), f=1;
    while ((c<'0' || c>'9') && c!='-') c=getchar();
    if (c=='-') f=-1, c=getchar();
    for (x=0; c>='0' && c<='9'; c=getchar())
        x=x*10+c-'0';
    x*=f;
}
const int N=505;
int n,d,r,al,dp[N][N];
long long s[N],f[N][N];
unordered_map<int,int>p;
int main(){
    in(n);in(d);in(r);
    for(int i=1;i<=n;i++){
        al+=r;if(al>=d)al-=d;
        if(p.count(al))break;
        p[al]=i;
    }
    for(int i=1;i<=n;i++){
        in(s[i]);
        if(s[i]%d==r)dp[i][i]=1,f[i][i]=s[i]/d;
        s[i]+=s[i-1];
    }
    for(int l=1;l<n;l++){
        for(int i=n-l;i;i--){
            int j=i+l,mx=0;
            for(int k=i;k<j;k++){
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
                mx=max(mx,dp[i][k]+dp[k+1][j]);
            }
            long long xx=(s[j]-s[i-1])%d;
            if(p.count(xx)&&p[xx]==mx+1)mx++;//如果res=0似乎会使mx变大(用0张巻白吃?)
            //但res=0如果出现,就一定是最后一项,也就是所有可达余数都已经能被计算出来了,多统计无影响
            dp[i][j]=mx;
            if(p.count(xx)&&mx>=p[xx])f[i][j]=max(f[i][j],(s[j]-s[i-1]-p[xx]*1ll*r)/d);
        }
    }
    cout<<f[1][n];
    return 0;
}
/*
dp[i][j]->区间[i,j]至多能参加几场婚礼
f[i][j]->区间[i,j]的答案
显然,只要需求可达且不超过dp[i][j],都能凑出来
*/