沙子合并加強

沙子合并問題

問題描述：設有N堆沙子排成一排，其編號為1，2，3，…，N(N<=2000)。每堆沙子有一定的數量，可以用一個整數來描述，現在要將這N堆沙子合并成為一堆，每次只能合并相鄰的兩堆，合并的代價為這兩堆沙子的數量之和，合并后與這兩堆沙子相鄰的沙子將和新堆相鄰，合并時由于選擇的順序不同，合并的總代價也不相同，如有4堆沙子分別為 1 ?3 ?5 ?2 我們可以先合并1、2堆，代價為4，得到4 5 2 又合并 1，2堆，代價為9，得到9 2 ，再合并得到11，總代價為4+9+11=24，如果第二步是先合并2，3堆，則代價為7，得到4 7，最后一次合并代價為11，總代價為4+7+11=22；問題是：找出一種合理的方法，使總的代價最小。輸出最小代價。

輸入：

第一行一個數N表示沙子的堆數N。

第二行N個數，表示每堆沙子的質量。

輸出：

合并的最小代價以及每一步合并的方法(輸出每次合并后的沙子的最小編號和最大編號)

樣例：

輸入：

4

13 7 6 5

輸出:

60

3 4

2 4

1 4

來，先看看，找不同

總結一下第一題數據范圍300，第二題范圍不變，但是變成了一個環，第三題數據范圍變成了2000

樸素的沙子合并算法

dp(i,j)表示把i到j這一段沙子合并成為一堆沙子，所需要的最小代價

那么一定是由某兩堆合并而來的

所以dp(i,j)=min{dp(i,k)+dp(k+1,j)}+sum[j]-sum[i-1]

這樣的算法O(n^3)只能過第一個吧

沒事，老大被解決了

第二題是環形的

如果每個起始位置都被枚舉一遍的話

就是O(n^4)，過不了，所以，我們力求一個更加高效的算法。

解決問題題的方法有兩種，一種是繼承，這里不討論，還有一種是展環為鏈(一種解決環形dp的最佳方法)

我們復制序列一遍，將它粘貼在第一個序列的末尾，構成2n-1的序列，然后對這個序列做區間dp

所以最佳解一定是一個子問題，這下子復雜度最高(2n-1)^2,可以勉勉強強的過吧

然后第三題就麻煩了n<=2000

n^3絕對超時，腫么辦呢。

這就是一套全新的理論，四邊形優化

理論如下

DP的四邊形優化

一、進行四邊形優化需要滿足的條件

1、狀態轉移方程如下：

m(i,j)表示對應i,j情況下的最優值。

w(i,j)表示從i到j的代價。

例如在合并石子中：

m(i,j)表示從第i堆石子合并到j堆石子合并成一堆的最小代價。

w(i,j)表示從第i堆石子到第j堆石子的重量和。

2、函數w滿足區間包含的單調性和四邊形不等式

二、滿足上述條件之后的兩條定理

1、假如函數w滿足上述條件，那么函數m也滿足四邊形不等式，即

例如:

假如有：w(1,?3) +?w(2, 4) ￡?w(2,?3) +?w(1,?4)，

m(1,?3) +?m(2, 4) ￡?m(2,?3) +?m(1,?4)，

2、假如m(i, j)滿足四邊形不等式，那么s (i, j)單調，即：

m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(i≤k≤j)(min也可以改為max)

上述的m(i,j)表示區間[i,j]上的某個最優值。w(i,j)表示在轉移時需要額外付出的代價。該方程的時間復雜度為O(N3)

下面我們通過四邊形不等式來優化上述方程，首先介紹什么是“區間包含的單調性”和“四邊形不等式”

1、區間包含的單調性：如果對于 i≤i'

2、四邊形不等式：如果對于 i≤i'

下面給出兩個定理：

1、如果上述的 w 函數同時滿足區間包含單調性和四邊形不等式性質，那么函數 m 也滿足四邊形不等式性質

我們再定義 s(i,j) 表示 m(i,j) 取得最優值時對應的下標(即 i≤k≤j 時，k 處的 w 值最大，則 s(i,j)=k)。此時有如下定理

2、假如 m(i,j) 滿足四邊形不等式，那么 s(i,j) 單調，即 s(i,j)≤s(i,j+1)≤s(i+1,j+1)。

好了，有了上述的兩個定理后，我們發現如果w函數滿足區間包含單調性和四邊形不等式性質，那么有 s(i,j-1)≤s(i,j)≤s(i+1,j) 。

即原來的狀態轉移方程可以改寫為下式：

m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(s(i,j-1)≤k≤s(i+1,j))(min也可以改為max)

由于這個狀態轉移方程枚舉的是區間長度 L=j-i，而 s(i,j-1) 和 s(i+1,j) 的長度為 L-1，是之前已經計算過的，可以直接調用。

不僅如此，區間的長度最多有n個，對于固定的長度 L，不同的狀態也有 n 個，故時間復雜度為 O(N^2)，而原來的時間復雜度為 O(N^3)，實現了優化！

今后只需要根據方程的形式以及 w 函數是否滿足兩條性質即可考慮使用四邊形不等式來優化了。

以上描述狀態用 m(i,j)，后文用的 dp[i][j]，所代表含意是相同的，特此說明。

以石子合并問題為例。

例如有６堆石子，每堆石子數依次為３ ４ ６ ５ ４ ２

因為是相鄰石子合并，所以不能用貪心(每次取最小的兩堆合并)，只能用動歸。(注意：環形石子的話，必須要考慮最后一堆和第一堆的合并。)

例如：一個合并石子的方案：

第一次合并 ３ ４ ６ ５ ４ ２ ->７

第二次合并 ７ ６ ５ ４ ２ ->１３

第三次合并 １３ ５ ４ ２ ->６

第四次合并 １３ ５ ６ ->１１

第五次合并 １３ １１ ->２４

總得分＝７＋６＋１１＋１３＋２４＝６１ 顯然，比貪心法得出的合并方案(得分：62)更優。

動歸分析類似矩陣連乘等問題，得出遞推方程：

設 dp[i][j] 表示第 i 到第 j 堆石子合并的最優值，sum[i][j] 表示第 i 到第 j 堆石子的總數量。

(可以在計算開始先做一遍求所有的 sum[i]，表示求出所有第1堆到第i堆的總數量。則 sum[i][j]=sum[j]-sum[i]。這樣計算比較快。)

那么就有狀態轉移公式：

這里 i<=k

普通解法需要 O(n^3)。下面使用四邊形不等式進行優化。

首先判斷是否符合區間單調性和四邊形不等式。

i ?i' ? ?j ? ?j'

3 4 6 5 4 2

單調性：

w[i',j] = 4+6+5=15 w[i,j'] =3+4+6+5+4+2=24

故w[i',j] <= w[i,j'] 滿足單調性

四邊形不等式：

w[i,j] + w[i',j'] = (3+4+6+5) + (4+6+5+4+2) = 18+21 = 39

w[i',j] + w[i,j'] = (4+6+5) + (3+4+6+5+4+2) = 15 + 24 = 39

故 w[i,j] + w[i',j'] <= w[i',j] + w[i,j']

故石子合并可利用四邊形不等式進行優化。

利用四邊形不等式，將原遞推方程的狀態轉移數量進行壓縮(即縮小了k的取值范圍)。

令 s[i][j]=min{k | dp[i][j] = dp[i][k-1] + dp[k][j] + w[i][j]}，即計算出 dp[i][j] 時的最優的 k 值(本例中尋優為取最小)

也可以稱為最優決策時的 k 值。由于決策 s 具有單調性，因此狀態轉移方程中的 k 的取值范圍可修改為 :

s[i,j-1] <= s[i,j] <= s[i+1,j]

邊界：s[i,i] = i

因為 s[i,j] 的值在 m[i,j] 取得最優值時，保存和更新，因此 s[i,j-1] 和 s[i+1,j] 都在計算 dp[i][j-1] 以及 dp[i+1][j] 的時候已經計算出來了。

因此，s[i][j] 即 k 的取值范圍很容易確定。

根據改進后的狀態方程，以及 s[i][j] 的定義方程，可以很快的計算出所有狀態的值。計算過程可以如下表所示(類似于矩陣連乘的打表)。

狀態表(如果是環形石子合并，需要打2n*2n的表)

3 4 6 5 4 2

例如：

計算dp[1][3]，由于s[1][2]=1，s[2][3]=2，則k值的取值范圍是1<=k<=2

則，dp[1][3]=min{dp(1,1)+dp(2,3)+13, dp(1,2)+dp(3,3)+13}=min{10+13, 7+13}=20，將其填到狀態表。同時，由于取最優值的k等于2，則將其填到s表。

同理，可以計算其他狀態表和s表中的值。

dp[2][4]=min{dp(2,2)+dp(3,4)+15, dp(2,3)+dp(4,4)+15}=min{11+15, 10+15}=25

k=3

從表中可以看出，當計算dp[2][5]的時候，由于s[ i,j-1]=s[ 2,4]=3，s[ i+1,j]=s[3,5]=3，此時k的取值范圍已經限定為只有一個，大幅縮短了尋找最優解的時間。

于是乎，復雜度降到了O(n^2)

厲害吧O(∩_∩)O哈哈~

附上代碼

#include#include#include#include#include#include#include#include#include#include#include

#define mod 998244353

#define N 100005

#define pi acos(-1)

#define inf 0x7fffffff

#define ll long long

using namespacestd;

ll read()

{

ll x=0,f=1;char ch=getchar();while(ch'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;

}intn;int a[305],sum[305];int f[305][305];int dp(int l,intr)

{if(f[l][r]!=-1)returnf[l][r];if(l==r)return 0;int ans=inf;for(int i=l;i

ans=min(ans,dp(l,i)+dp(i+1,r));return f[l][r]=(ans+sum[r]-sum[l-1]);

}intmain()

{

memset(f,-1,sizeof(f));

n=read();for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];

printf("%d\n",dp(1,n));return 0;

}

#include#include

using namespacestd;int v[1001],sum[1001],f[1001][1001];intmain()

{int n,mi=9999999;

scanf("%d",&n);for(int i=1;i<=2*n-1;i++)for(int j=i+1;j<=2*n-1;j++)

f[i][j]=999999;int p=0;for(int i=1;i<=n;i++)

{

scanf("%d",&v[i]);

sum[i]=sum[i-1]+v[i];

}for(int i=1;i

{

v[++p]=v[i];

sum[p+n]=sum[p+n-1]+v[i];

}for(int i=2*n-1;i>=1;i--)for(int j=i+1;j<=i+n-1;j++)for(int k=i;k

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

mi=min(mi,f[i][i+n-1]);

printf("%d",mi);return 0;

}

#include#include

#define N 2000+1

#define INF 0x3fffffff

using namespacestd;intv[N],sum[N];structdata{intval,des;

};

data f[N][N];void output(int k,int i,intj);intmain()

{intn;

scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)

f[i][j].val=INF;for(int i=1;i<=n;i++)

{

scanf("%d",&v[i]);

sum[i]=sum[i-1]+v[i];

f[i][i].des=i;

}for(int i=n;i>=1;i--)for(int j=i+1;j<=n;j++)

{int begin=f[i][j-1].des;int end=min(j-1,f[i+1][j].des);for(int k=begin;k<=end;k++)

{if(f[i][j].val>f[i][k].val+f[k+1][j].val+sum[j]-sum[i-1])

{f[i][j].des=k;f[i][j].val=f[i][k].val+f[k+1][j].val+sum[j]-sum[i-1];}

}

}

printf("%d\n",f[1][n].val);

output(f[1][n].des,1,n);//printf("%d",f[1][n].des);

return 0;

}void output(int k,int i,intj)

{if(i==j)return;

output(f[i][k].des,i,k),output(f[k+1][j].des,k+1,j);

printf("%d %d\n",i,j);

}

總結

以上是生活随笔為你收集整理的java怎么做沙子合并_dp之沙子合并 环形沙子合并 沙子合并加强 沙子三兄弟的故事...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。