?
用w[i][j]表示i到j之间没有边毁掉的费用。
有一种很好证明w[i][j]是否满足四边形不等式的条件. 若（w[i+1][j]-w[i][j]）是关于j的减函数，就是满足条件的。可以证明这里的w[i][j]是瞒住条件的。
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int inf = 0x3fffffff; const int mmax =1010; int w[mmax]; int sum[mmax]; int f[mmax]; int dp[mmax][mmax]; int S[mmax][mmax]; int cost[mmax][mmax]; int main() { int n,m; while(cin>>n>>m && n+m) { w[0]=0; sum[0]=0; f[0]=0; for(int i=1;i<=n;i++) { scanf(%d,&w[i]); sum[i]=sum[i-1]+w[i]; f[i]=sum[i]*w[i]+f[i-1]; } for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) cost[i][j]=(sum[j-1]-sum[i-1])*sum[j]-(f[j-1]-f[i-1]); dp[0][0]=0; for(int i=1;i<=n;i++) { dp[0][i]=cost[1][i]; S[0][i]=0; } for(int i=1;i<=m;i++) { dp[i][0]=0; S[i][n+1]=n; for(int j=n;j>=1;j--) { dp[i][j]=inf; int l=S[i-1][j],r=S[i][j+1]; for(int k=l;k<=min(j-1,r);k++) { if(dp[i][j]>dp[i-1][k]+cost[k+1][j]) { dp[i][j]=dp[i-1][k]+cost[k+1][j]; S[i][j]=k; } } } } printf(%d ,dp[m][n]); } return 0; }