| 比赛 |
csp2025模拟练习2 |
评测结果 |
AAAAAAAAAAAAAAA |
| 题目名称 |
Chocolate Bar Partition |
最终得分 |
100 |
| 用户昵称 |
wdsjl |
运行时间 |
1.540 s |
| 代码语言 |
C++ |
内存使用 |
15.36 MiB |
| 提交时间 |
2025-10-29 11:11:39 |
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+10;
const int inf = 1e9;
int dp[N][3],s[N][3],n,a[N][3],sum;
struct node{
int v;
node(){
v=-inf;
}
};
map<int,node>mp[4];
signed main(){
freopen("Chocolate.in","r",stdin);
freopen("Chocolate.out","w",stdout);
scanf("%lld",&n);
for(int i=0;i<=1;i++){
for(int j=1;j<=n;j++){
scanf("%lld",&a[j][i]);
sum+=a[j][i];
a[j][i]*=2*n;
}
}
for(int i=0;i<=1;i++){
for(int j=1;j<=n;j++){
a[j][i]-=sum;
}
}
for(int i=0;i<=1;i++){
for(int j=1;j<=n;j++){
s[j][i]=s[j-1][i]+a[j][i];
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=1;j++){
if(mp[j][s[i-1][j]].v<dp[i-1][j^1]){
mp[j][s[i-1][j]].v=dp[i-1][j^1];
}
if(mp[j|2][s[i-1][j^1]].v<dp[i-1][j]){
mp[j|2][s[i-1][j^1]].v=dp[i-1][j];
}
}
for(int j=0;j<=1;j++){
dp[i][j]=max(dp[i-1][0],dp[i-1][1]);//当前列两格均划入非零连通块
dp[i][j]=max(dp[i][j],mp[j^1][s[i][j^1]].v+1);//另一行末尾若干格子单独成块
dp[i][j]=max(dp[i][j],mp[(j^1)|2][-s[i][j^1]].v+1);//另一行末尾格子与前非零连通块拼合
}
if(s[i][0]+s[i][1]==0){//前 i 列总和平为 0
dp[i][0]=dp[i][1]=max(dp[i][0],dp[i][1])+1;
}
}
printf("%lld\n",dp[n][0]);
return 0;
}