石子合并（一）

時間限制：1000 ms ?|? 內(nèi)存限制：65535 KB

難度：3

描述

????有N堆石子排成一排，每堆石子有一定的數(shù)量。現(xiàn)要將N堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費(fèi)的代價為這兩堆石子的和，經(jīng)過N-1次合并后成為一堆。求出總的代價最小值。

輸入

有多組測試數(shù)據(jù)，輸入到文件結(jié)束。
每組測試數(shù)據(jù)第一行有一個整數(shù)n，表示有n堆石子。
接下來的一行有n（0< n <200）個數(shù)，分別表示這n堆石子的數(shù)目，用空格隔開

輸出

輸出總代價的最小值，占單獨(dú)的一行

樣例輸入

3 1 2 3 7 13 7 8 16 21 4 18

樣例輸出

9 239

來源

經(jīng)典問題

分析

第一步：確定狀態(tài)

f[i,j]表示合并i到j的所有石子的得分

第二步：確定狀態(tài)轉(zhuǎn)移方程

f[i,j] = max(f[i][j]， f[i][k] + f[k + 1][j] + sum[i][j])

sum[i][j] 表示i到j的石子的價值和。邊界：f[i][i] = 0

#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f //#define inf 1<<20 const int maxn=210; int n,a[maxn]; int dp[maxn][maxn];//dp[i][j]表示從第i堆到第j堆合并的代價 int sum[maxn][maxn];//表示石頭的數(shù)量 int main() {ios::sync_with_stdio(0);while(cin>>n){for(int i=1;i<=n;i++)cin>>a[i];memset(sum,0,sizeof(sum));//fill(dp[0],dp[0]+n*n,inf);//錯誤 fill(dp[0],dp[0]+maxn*maxn,inf);//fill填充量必須是常數(shù) /*for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)//dp[i][j]=inf; */ for(int i=1;i<=n;i++)sum[i][i]=a[i],dp[i][i]=0;for(int len=1;len<n;len++){//區(qū)間長度 for(int i=1;i<=n&&i+len<=n;i++){//區(qū)間起點(diǎn) int j=i+len;//區(qū)間終點(diǎn)for(int k=i;k<=j;k++)//用k來表示分割區(qū)間 {sum[i][j]=sum[i][k]+sum[k+1][j];dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);} }}cout<<dp[1][n]<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的NYOJ737 石子合并（一）区间动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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