題目描述

　　有一排石子，共n 堆?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2 堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試設(shè)計(jì)一個(gè)算法，計(jì)算出將n堆石子合并成一堆的最小得分。

題解

　　首先由直接動(dòng)態(tài)規(guī)劃的方法來(lái)做，即?

for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)for(int k=i;k<=j;k++){f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+cost[j]-cost[i-1]);}

　　但是如果N的值超過(guò)了3000的話，這個(gè)算法就明顯會(huì)爆炸的，所以我們應(yīng)當(dāng)采取一定的優(yōu)化，經(jīng)過(guò)計(jì)算我們可以發(fā)現(xiàn)這個(gè)題目是滿足四邊形不等式的，這里所用的優(yōu)化呢是四邊形不等式優(yōu)化。

　　我們定義階段為區(qū)間長(zhǎng)度len，狀態(tài)為f[i][j]合并i到j(luò)的最小費(fèi)用。

　　注意：因?yàn)槲覀兊碾A段決定了，在計(jì)算s[i][j]時(shí)，s[i][j-1]和s[i+1][j]都已經(jīng)計(jì)算出來(lái)了

代碼

//FZOJ1555 合并石子（求最小值）四邊形不等式優(yōu)化 #include<bits/stdc++.h> using namespace std; int f[101][101],s[101][101],a[101],sum[101],q; int main() {int i,j,k,n,len,q;scanf("%d",&n);memset(sum,0,sizeof(sum));memset(f,60,sizeof(f));memset(s,0,sizeof(s));for(i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];} for(i=1;i<=n;i++){f[i][i]=0;s[i][i]=i;}for(len=1;len<n;len++)for(i=1;i<=n-len;i++){j=i+len;q=sum[j]-sum[i-1];for(k=s[i][j-1];k<=s[i+1][j];k++){if(f[i][j]>f[i][k]+f[k+1][j]+q){f[i][j]=f[i][k]+f[k+1][j]+q;s[i][j]=k;}}}printf("%d\n",f[1][n]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/2020pengxiyue/p/8178818.html

總結(jié)

以上是生活随笔為你收集整理的合并石子 四边形不等式优化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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