題目大意：將n個數(shù)分成m組，將每組的最大值與最小值的平方差加起來，求最小和。

題目分析：先對數(shù)排序。定義狀態(tài)dp(i,j)表示前 j 個數(shù)分成 i 組得到的最小和，則狀態(tài)轉(zhuǎn)移方程為dp(i,j)=min(dp(i,k-1)+w(k,j))，其中w(i,j)=(a[i]-s[j])*(a[i]-a[j])。很顯然，dp(i,j)滿足凸四邊形不等式。

?

代碼如下：

# include<iostream> # include<cstdio> # include<cstring> # include<algorithm> using namespace std;const int INF=1<<30; int dp[10005][505]; int K[10005][505]; int a[10005]; int n,m;void read() {scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%d",a+i); }int solve() {sort(a+1,a+n+1);for(int i=1;i<=n;++i){dp[1][i]=(a[i]-a[1])*(a[i]-a[1]);K[1][i]=0;if(i<=m){dp[i][i]=0;K[i][i]=i;}}for(int i=2;i<=m;++i){K[i][n+1]=n;for(int j=n;j>=i;--j){dp[i][j]=INF;for(int k=K[i-1][j];k<=K[i][j+1];++k){if(dp[i][j]>dp[i-1][k-1]+(a[j]-a[k])*(a[j]-a[k])){dp[i][j]=dp[i-1][k-1]+(a[j]-a[k])*(a[j]-a[k]);K[i][j]=k;}}}}return dp[m][n]; }int main() {int T,cas=0;scanf("%d",&T);while(T--){read();printf("Case %d: %d\n",++cas,solve());}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/20143605--pcx/p/5294606.html

總結(jié)

以上是生活随笔為你收集整理的HDU-3480 Division （四边形不等式优化DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。