题目思路：动态规划 n^3
dp[i][j] 表示前 i 匹马分成 j 堆总的忧愁度。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 1005 #define maxn 100005 typedef pair<int,int> PII; typedef long long LL; int n,m,k; int a[N]; int dp[N][N]; int num1[N],num2[N]; int main(){ int i,j,group; //freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); if(m>=n){ printf("0 "); return 0; } for(i=1;i<=n;++i){ scanf("%d",&a[i]); num1[i]=num1[i-1]; num2[i]=num2[i-1]; if(a[i])++num1[i]; else ++num2[i]; } for(i=1;i<=n;++i){ dp[i][1]=num1[i]*num2[i]; for(j=2;j<=i;++j){ dp[i][j]=inf; if(i==j)dp[i][j]=0; for(int k=j-1;k<i;++k){ dp[i][j]=min(dp[i][j],dp[k][j-1]+(num1[i]-num1[k])*(num2[i]-num2[k])); } } } printf("%d ",dp[n][m]); return 0; }