題目:有n堆石子排成一列,每堆石子有一個重量w[i], 每次合并可以合并相鄰的兩堆石子,一次合并的代價為兩堆石子的重量
和w[i]+w[i+1]。問安排怎樣的合并順序,能夠使得總合并代價達到最小。
輸入:
第一行一個整數n(n<=100)
第二行n個整數w1,w2...wn (wi <= 100)
輸出:一個整數表示最小合并代價
這是一個比較經典的動态規劃問題,對于給定的石子,當合并完後,隻會剩餘一堆石子,而這一堆石子是由兩堆石子合并而來的。
通過倒推可以知道,第i~j堆已合并石子可以由i~k堆已合并石子與k~j堆已合并石子合并而來(i<=k<=j)。即dp[i][j]=dp[i][k]+dp[k][j]
+sum[i][j];(sum[i][j]為這堆石子的合并代價)
于是可以有
for(j=1;j<=n;j++)
{
for(i=j-1;i>0;i--)
{
dp[i][j]=dp[i][i]+dp[i+1][j]+sum[i][j];
for(k=i+1;k<j;k++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);
}
}
}
其中dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);是找出第i~j堆石子合并的的最小帶價。下面是全代碼:
#include<iostream>
#include<cstring>
using namespace std;
int min(int a,int b)//找出a,b的最小值。
{
if(a>b) return b;
else return a;
}
int main()
{
int sum[101][101],dp[101][101],w[101];
memset(sum,0,sizeof(sum));
memset(dp,0,sizeof(dp));
int n,i,j,k;
cin>>n;
for(i=1;i<=n;i++)//讀入每個石子堆對應的代價。
{
cin>>w[i];
}
for(i=1;i<=n;i++)//計算從i到j的石子堆的總代價,用sum[i][j]表示。
{
sum[i][i]=w[i];
for(j=i+1;j<=n;j++)
{
sum[i][j]=sum[i][j-1]+w[j];
}
}
for(j=1;j<=n;j++)//通過動态規劃找出最優的代價。
{
for(i=j-1;i>0;i--)
{
dp[i][j]=dp[i][i]+dp[i+1][j]+sum[i][j];
for(k=i+1;k<j;k++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);//dp[i][k],dp[k+1][j]表示合成這堆石子
//的前兩堆石子的合并的最小代價。
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}
執行個體:
輸入:4
4 1 1 4
輸出:18
程式分析:sum[1][1]=4,sum[1][2]=5,sum[1][3]=6,sum[1][4]=10,
sum[2][2]=1,sum[2][3]=2,sum[2][4]=6,...
dp[1][2]=5,dp[2][3]=2,dp[1][3]=8.
dp[1][2]+dp[2][3]+sum[1][3]=13
dp[1][3]=min(dp[1][3],dp[1][2]+dp[2][3]+sum[1][3])=8;
...
最後可得結果為 18,
轉載于:https://www.cnblogs.com/weifengxiyu/p/4399167.html