@[rainfox](/user/1033626) 本题是 $dp$ ，不是贪心
by danlao @ 2024-02-16 12:00:08
@[yaodiguoan](/user/1023793) 楼上正解，这题是 DP，贪心是不对的（当然如果把题面改成取任意两堆就是贪心了）
by masonxiong @ 2024-02-16 12:23:49
@[rainfox](/user/1033626) 这题是这样写的！
```cpp
#include <iostream>
#include <cstring>
using namespace std;
#define hh printf("\n")
#define kg printf(" ")
#define cg ch=getchar()
inline int read(){
int x=0,f=1;char cg;
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;cg;}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';cg;}
return x*f;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
int n,a[310],sum[310],dp[310][310];
int main(){
n=read();
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++){
a[i]=read();
dp[i][i]=0;
sum[i]=sum[i-1]+a[i];
}
for(int len=2;len<=n;len++)
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
for(int k=l;k<r;k++)
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
}
write(dp[1][n]);
return 0;
}
```
by danlao @ 2024-02-16 12:35:57
感谢各位大佬
by rainfox @ 2024-02-16 17:37:01