自动搬运

查看原文

来自洛谷，原作者为

	MoonCake2011 有朋自远方来，板砖呼，左手呼完右手呼，呼不S再呼||题目很少，很快就做完了。微笑着做完，才会胜利。||原 Libingyue2011||J:400->360->280 S:265->258

搬运于2025-08-24 23:14:40，当前版本为作者最后更新于2025-07-21 16:41:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

纯水题，就是几秒出思路，几分钟写代码的那种。

首先，我们先考虑区间 dp。

设 $dp_{i,j,k}$ 为区间 $[i,j]$ 合并完后颜色为 $k$ 的最小花费。

然后直接像这道题一样直接转移就是了。

我们求出每个区间的答案之后，我们可以继续考虑 dp。

因为要求最少的石头堆数，我们直接考虑分段 dp，每一段都是能合并成功的。

设 $f_{i,j}$ 为前 $i$ 个数分 $j$ 段的最小花费。

初值 $f_{0,0}=0$。

然后直接可以列出转移方程。

$$f_{i,j}=\sum_{k=0}^{i-1} f_{k,j-1}+\min_{0\le c\le 2}(dp_{k+1,c})$$。 接着我们从小到大枚举段数，第一个有值的 $dp_{n,i}$ 就是答案。 代码。 ```cpp #include 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<<" "<