P12789 [ICPC 2024 Yokohama R] Peculiar Protocol

存在一个显然的性质：对于任意一个区间

\left [ l,r \right ]

，设用其中元素至多能参加

x

场婚礼，那么对于任意

y \le x

，都可以找到一种合法的方案。

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

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

d

取模是否为

r

即可。

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

其余细节可以见代码。

代码

CPP

#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],都能凑出来
*/

P12789 [ICPC 2024 Yokohama R] Peculiar Protocol

文章操作

代码

相关推荐

评论

P12789 [ICPC 2024 Yokohama R] Peculiar Protocol