题解：AT_joi2026_yo2_b 究極の団子職人 (Ultimate Dango Maker)
mjs137891
·
·
题解
题解
思路
这题就是凑团子。每个颜色先自己凑，够仨串一串，剩下的余数只有 0、1、2 ，只能找邻居搭伙。
余数最多俩，所以一个颜色最多只能跟一边凑。从左往右扫就行，只需要记住上一个颜色剩了几个给我。
$A[i]+j$ ，枚举留给下一个 $k$ 个，本轮用掉 $A[i]+j-k$ 个，并且上一个剩的 $j$ 个必须用完。
$j$ 只有 $0、1、2$ ，直接暴力枚举怎么混合：拿 $1$ 个去混合对面出 $2$ 个，拿 $2$ 个去混合对面出 $1$ 个，剩下的继续仨仨凑纯色，取最大值。复杂度 $O(N)$ 。
:::success[AC CODE]{close}
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int N; cin>>N;
vector<ll> A(N);
for(int i=0;i<N;i++) cin>>A[i];
const ll NEG=-(1LL<<60);
vector<vector<ll>> dp(N+1,vector<ll>(3,NEG));
dp[0][0]=0;
for(int i=0;i<N;i++) {
for(int rem=0;rem<3;rem++) {
if(dp[i][rem]==NEG) continue;
ll total=A[i]+rem;
for(int nxt=0;nxt<3;nxt++) {
if(total<nxt) continue;
ll use=total-nxt;
if(use<rem) continue;
ll cur=use-rem;
ll best=0;
for(int x=0;x<=rem;x++){
if(x==0){
if(rem==0) best=max(best,cur/3);
}else{
int need=3-x;
if(cur>=need) best=max(best,1+(cur-need)/3);
}
}
dp[i+1][nxt]=max(dp[i+1][nxt],dp[i][rem]+best);
}
}
}
cout<<dp[N][0];
return 0;
}
```
:::