题解：P12330 [蓝桥杯 2023 省 Java B] 合并石子
MoonCake2011
·
·
题解
纯水题，就是几秒出思路，几分钟写代码的那种。
首先，我们先考虑区间 dp。
设 dp_{i,j,k} 为区间 [i,j] 合并完后颜色为 k 的最小花费。
然后直接像这道题一样直接转移就是了。
我们求出每个区间的答案之后，我们可以继续考虑 dp。
因为要求最少的石头堆数，我们直接考虑分段 dp，每一段都是能合并成功的。
设 f_{i,j} 为前 i 个数分 j 段的最小花费。
初值 f_{0,0}=0。
然后直接可以列出转移方程。
接着我们从小到大枚举段数，第一个有值的 $dp_{n,i}$ 就是答案。
代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100010],c[100010],s[100010];
int dp[310][310][3],f[310][310];
signed main() {
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
for(int i=1;i<=n;i++) cin>>c[i];
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n;i++) dp[i][i][c[i]]=0;
for(int k=2;k<=n;k++){
for(int i=1;i+k-1<=n;i++){
int j=i+k-1;
for(int p=i;p<j;p++){
dp[i][j][0]=min(dp[i][j][0],dp[i][p][2]+dp[p+1][j][2]+s[j]-s[i-1]);
dp[i][j][1]=min(dp[i][j][1],dp[i][p][0]+dp[p+1][j][0]+s[j]-s[i-1]);
dp[i][j][2]=min(dp[i][j][2],dp[i][p][1]+dp[p+1][j][1]+s[j]-s[i-1]);
}
}
}
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){//分几段
for(int k=0;k<i;k++) f[i][j]=min(f[i][j],f[k][j-1]+min(dp[k+1][i][0],min(dp[k+1][i][1],dp[k+1][i][2])));
}
}
for(int i=1;i<=n;i++) if(f[n][i]<=2e15){
cout<<i<<" "<<f[n][i];
break;
}
return 0;
}
```