題意：多邊形游戲是一個單人玩的游戲，開始時有一個由n個頂點構成的多邊形。每個頂點被賦予一個整數值，每條邊被賦予一個運算符“+”或“*”。所有邊依次用整數從1到n編號
游戲第1步，將一條邊刪除
隨后n-1步按以下方式操作
(1)選擇一條邊E以及由E連接著的2個頂點V1和V2
(2)用一個新的頂點取代邊E以及由E連接著的2個頂點V1和V2。將由頂點V1和V2的整數值通過邊E上的運算得到的結果賦予新頂點
最后，所有邊都被刪除，游戲結束。游戲的得分就是所剩頂點上的整數值； 這道題很有意思，也比較有難度，是一個算式形式的動態規劃，和區間dp還是有一定聯系的，因為我們每次開始游戲時需要斷開一條邊，之后就變成了一條鏈，可以看做區間，這樣，我們初步應該會想到f[l][r]來表示l到r合并后最大的價值。 ！！但是，這樣就會有一個非常謎的問題！最大值不僅是由最大值加和而來的，它還可能是由兩個最小值乘來的（負負得正)，這樣題就沒法做了，所以這個子問題不滿足無后效性！只能另尋它法！雖然說這個子問題不合適，但是這離我們的正解也已經非常近了。 我們可以用f[l][r]表示l到r所能合成的最大值，然后f1[l][r]表示l到r能合成的最小值。為什么這就能滿足無后效性呢，因為啊： 1.一個最大值無非就是由兩個最大值相加，兩個最大值相乘或者兩個最小值相乘而得來的！ 2.一個最小值無非就是由兩個最小值相加，或兩個最小值相乘，或前一個最小值和后一個最大值相乘，或后一個最小值和前一個最大值相乘而得來的！ 所以，我們就能夠依據上述關系寫出狀態轉移方程，這里就不給出了； 這樣呢，我們就能夠用區間dp的套路安排循環！但是有一個巨大的問題，我們需要枚舉首先斷掉那條邊！這樣下來會很麻煩，怎么辦呢。在處理動態規劃的環形問題時，我們可以先把這個環斷掉，從任意位置斷掉，然后長度復制一條一模一樣的鏈連接在其后，這樣我們就可以通過區間的移動來達成首先斷一條邊的操作；因為區間每次向右移動一位，都代表著把原來斷的那條邊接上，在把現有的最左邊這條邊斷掉！這樣就能達成一個。枚舉先斷哪條邊的作用！ 于是這道題完美解決，下面看代碼！ 1 //怕你飛遠去 2 //怕你離我而去 3 //更怕你永遠停留在這里 4 #include<iostream> 5 #include<cstdio> 6 #include<cstdlib> 7 #include<cstring> 8 #include<string> 9 #include<cmath> 10 #include<algorithm> 11 #include<queue> 12 using namespace std; 13 const int MAXN=125; 14 int f[MAXN][MAXN],f1[MAXN][MAXN],a[MAXN],n;//f[l][r]代表區間l到r所能合成的最大值，f1[l][r]表示區間l到r所能合成的最小值； 15 char b[MAXN]; 16 int main() 17 { 18 scanf("%d",&n); 19 memset(f,-0x3f,sizeof(f));//初始化； 20 memset(f1,0x3f,sizeof(f1));//初始化； 21 for(int i=1;i<=n;i++){ 22 getchar(); 23 scanf("%c%d",&b[i],&a[i]); 24 b[i+n]=b[i];a[i+n]=a[i];//斷開，復制成一個兩倍長度的鏈； 25 } 26 for(int i=1;i<=2*n;i++){ 27 f1[i][i]=f[i][i]=a[i];//初始化； 28 }//區間Dp 29 for(int i=2;i<=n;i++){//階段（區間的長度） 30 for(int l=1;l<=n*2-i+1;l++){//狀態（左端點） 31 int r=l+i-1;//狀態（右端點） 32 for(int k=l;k<r;k++){//決策（嗯） 33 if(b[k+1]=='t'){ 34 f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);//最大值由兩個最大值相加而來 35 f1[l][r]=min(f1[l][r],f1[l][k]+f1[k+1][r]);//最小值由兩個最小值相加而來 36 } 37 else{ 38 f[l][r]=max(f[l][r],f[l][k]*f[k+1][r]);//最大值由兩個最大值相乘而來 39 f[l][r]=max(f[l][r],f1[l][k]*f1[k+1][r]);//最大值由兩個最小值相乘而來 40 f1[l][r]=min(f1[l][r],f1[l][k]*f1[k+1][r]);//最小值由兩個最小值相乘而來 41 f1[l][r]=min(f1[l][r],f[l][k]*f1[k+1][r]);//最小值由前一個最大值和后一個最小值相乘而來 42 f1[l][r]=min(f1[l][r],f1[l][k]*f[k+1][r]);//最小值由前一個最小值和后一個最大值相乘而來； 43 } 44 } 45 } 46 } 47 int maxx=-0x7fffffff; 48 for(int i=1;i<=n;i++){ 49 maxx=max(maxx,f[i][i+n-1]); 50 } 51 printf("%d",maxx); 52 puts(""); 53 for(int i=1;i<=n;i++){ 54 if(f[i][n-1+i]==maxx){//枚舉，尋找第一步最優策略，有幾個輸出幾個！ 55 printf("%d ",i); 56 } 57 } 58 puts(""); 59 return 0; 60 } View Code

?

轉載于:https://www.cnblogs.com/Alan-Luo/articles/8723289.html

總結

以上是生活随笔為你收集整理的POJ1179 Polygon 【例题精讲】的全部內容，希望文章能夠幫你解決所遇到的問題。

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