石子合并（一）

時間限制：1000?ms ?|? 內存限制：65535?KB 難度：3 描述

????有N堆石子排成一排，每堆石子有一定的數量?，F要將N堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費的代價為這兩堆石子的和，經過N-1次合并后成為一堆。求出總的代價最小值。 輸入

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

輸出

輸出總代價的最小值，占單獨的一行

樣例輸入

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

樣例輸出

9 239

AC碼：

#include<stdio.h> #include<string.h> #define INF 2000000005 int dp[203][203],sum[203]={0}; int DP(int left,int right) {if(dp[left][right]>=0) // 某一個區間左端到右端已經得到最優方案return dp[left][right];if(left==right) // 說明該區間就一堆石子{return dp[left][right]=0;}int min,mid;for(mid=left;mid<right;mid++){if(dp[left][right]<0)dp[left][right]=INF;// 核心：動態轉移方程min=DP(left,mid)+DP(mid+1,right)+(sum[mid]-sum[left-1])+(sum[right]-sum[mid]);if(min<dp[left][right])dp[left][right]=min;}return dp[left][right]; } int main() {int n,i,a;while(~scanf("%d",&n)){// n表示石子的堆數for(i=1;i<=n;i++){scanf("%d",&a); // a依次表示第i堆的石子數sum[i]=a+sum[i-1];}memset(dp,-1,sizeof(dp));printf("%d\n",DP(1,n));}return 0; } 區間DP問題！
#include<stdio.h> #define INF 2000000005 int dp[205][203],sum[203]; int min(int a,int b) {return a>b?b:a; } int main() {int n,a;while(~scanf("%d",&n)){for(int i=1;i<=n;i++){scanf("%d",&a);sum[i]=sum[i-1]+a;dp[i][i]=0;}// 區間DPfor(int count=2;count<=n;count++){ // 遍歷合并count=2堆、3堆、...n堆的情況for(int start=1;start<=n-count+1;start++){ // start表示每個區間的始點int end=start+count-1; // end表示對應的該區間的終點dp[start][end]=INF;for(int mid=start;mid<=end;mid++){dp[start][end]=min(dp[start][end],dp[start][mid]+dp[mid+1][end]+sum[end]-sum[start-1]);}}}printf("%d\n",dp[1][n]);}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 737 合并石子(一)的全部內容，希望文章能夠幫你解決所遇到的問題。

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