題目描述

在一個(gè)圓形操場(chǎng)的四周擺放N堆石子,現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相鄰的2堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。

試設(shè)計(jì)出1個(gè)算法,計(jì)算出將N堆石子合并成1堆的最小得分和最大得分.

輸入輸出格式

輸入格式：

數(shù)據(jù)的第1行試正整數(shù)N,1≤N≤100,表示有N堆石子.第2行有N個(gè)數(shù),分別表示每堆石子的個(gè)數(shù).

輸出格式：

輸出共2行,第1行為最小得分,第2行為最大得分.

輸入輸出樣例

輸入樣例#1：

4
4 5 9 4

輸出樣例#1：

43
54

思路：

用 dp_min[i][j] 來(lái)表示合并第 i 堆到第 j 堆石子的最小代價(jià)，用 dp_max[i][j] 來(lái)表示合并第 i 堆到第 j 堆石子的最大代價(jià)。

那么狀態(tài)轉(zhuǎn)移方程為：

dp_min[j][i] = min(dp_min[j][i],dp_min[j][k]+dp_min[(j+k+1)%n][i-k-1]+judge(j,i));
dp_max[j][i] = max(dp_max[j][i],dp_max[j][k]+dp_max[(j+k+1)%n][i-k-1]+judge(j,i));

其中?judge(j,i) 表示把兩部分合并起來(lái)的代價(jià)，用 sum[i] 表示從第 1 堆到第 i 堆的石子個(gè)數(shù)和

源代碼

#include <iostream> using namespace std;int max(int x,int y)//求最大值 {if(x>y)return x;elsereturn y; } int min(int x,int y)//求最小值 {if(x>y)return y;elsereturn x; }int n,sum[300]; int judge(int i,int j) { if(i+j>=n)//若大于堆數(shù)return judge(i,n-i-1)+judge(0,(i+j)%n);//進(jìn)行循環(huán)判斷else//若小于堆數(shù)return sum[i+j]-(i>0?sum[i-1]:0);//判斷進(jìn)行合并的值 }int main() {int stone[300];int dp_min[300][300]={0},dp_max[300][300]={0}; int i,j,k;int min_score,max_score;cin>>n;//輸入石頭堆數(shù)for(i=0;i<n;i++) cin>>stone[i];//輸入每堆個(gè)數(shù)sum[0]=stone[0];//第一堆個(gè)數(shù)for(i=1;i<n;i++) sum[i]=sum[i-1]+stone[i];//計(jì)算當(dāng)前堆數(shù)及其前面所有堆數(shù)的和for(i=1;i<n;i++)//合并n-1次{for(j=0;j<n;j++)//判斷每堆是否合并{dp_min[j][i]=999999;dp_max[j][i]=0;for(k=0;k<i;k++)//依次判斷到當(dāng)前合并次數(shù){ dp_min[j][i] = min(dp_min[j][i],dp_min[j][k]+dp_min[(j+k+1)%n][i-k-1]+judge(j,i));//最小值dp_max[j][i] = max(dp_max[j][i],dp_max[j][k]+dp_max[(j+k+1)%n][i-k-1]+judge(j,i));//最大值}}}for(i=0;i<n;i++){ min_score=min(min_score,dp_min[i][n-1]);//尋找最小值max_score=max(max_score,dp_max[i][n-1]);//尋找最大值}cout<<min_score<<endl;//最小值cout<<max_score<<endl;//最大值return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的石子合并（洛谷-P1880）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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