題目描述】

多邊形游戲是一種在一個具有n個頂點的多邊形上進(jìn)行的游戲。每個頂點有個權(quán)值（整

數(shù)）。如圖1是一個n=4對應(yīng)多邊形，每個頂點上都有一個整數(shù)，每條邊都有一個運算符+或者*，所有邊按從1到n進(jìn)行編號。

游戲都首先移除一條邊，接下來可以進(jìn)行如下操作：

選擇一條邊E和與之相關(guān)聯(lián)的點V1和V2，用一個新的點替換它們，新點上的整數(shù)為V1,V2上的整數(shù)用E上的操作符運算后的結(jié)果。

沒有邊時游戲結(jié)束，游戲得分就是最后剩下的那個頂點上的整數(shù)。

對于圖1中的多邊形，如果游戲者首先去掉3，然后依次去掉1、4、2，最后得分將是0。

請你寫一個程序，對于給定的多邊形，計算出可能得到的最高分，并列出第一步移除哪些邊可以得到這個最高分。

【輸入格式】

輸入文件game.in共兩行，第一行是一個正整數(shù)n(3<=n<=50)，表示多邊形的邊數(shù)。

接下來一行是這個多邊形的描述，包含n條邊和n個頂點，加號邊用t表示，乘號邊用x表示，頂點用頂點上標(biāo)的整數(shù)表示，輸入按照邊的編號從1到n的順序給出。

【輸出格式】

輸出文件game.out共兩行，第一行輸出可能得到的最高分。

第二行輸出一些邊的列表，只有第一步移除的邊在這個列表中才可能得到最高分。每條邊都用這個邊上的編號表示，列表必須是升序的。

【輸入樣例】

4

t -7 t 4 x 2 x 5

【輸出樣例】

33

1 2

---

?

剛開始看到這道題，我就一直懵逼了，根本懶得寫，所以沒用想到我以前做過的叫 石子合并 的一題。

這題和那題很像，附上題解：

我們發(fā)現(xiàn)本題和石子合并很相似，則容易想到用f[i][j]表示區(qū)間[i,j]的最大值，但題目有一點不同是還要求首先刪掉的邊，所以狀態(tài)多一維f[x][i][j]表示首先刪掉x，合并區(qū)間[i,j]的最優(yōu)解。則方程為f[x][i][j] = max(f[x][i][j],f[x][i][k] +或* f[x][k + 1][j] )

注意，我們所關(guān)心的最大值不僅會由兩個大的正數(shù)相加或相乘得到，還可能會由兩個小的負(fù)數(shù)相乘得到，所以我們還需要用g[x][i][j]來存儲最小值。偽代碼如下：

枚舉邊

枚舉階段

枚舉起點

枚舉斷點

if(+)t1=f+f,t2=g+g;

else(*)t1=f*f,t2=g*g;

if(t1>f)f=t1;

if(t2>f)f=t2; // 負(fù)數(shù)乘負(fù)數(shù)可能更新最大值

if(t1<f)g=t1; // 負(fù)數(shù)乘正數(shù)可能更新最小值

if(t2<f)g=t2;

然后是我的代碼：

?

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #define il inline using namespace std; il int gi() {int x=0,y=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*y; } int f[101][101][101]; int g[101][101][101]; bool hao[101]; int num[101]; int sum[101][101]; int main() {freopen("game.in","r",stdin);freopen("game.out","w",stdout);memset(f,-128,sizeof(f));int n=gi();for(int i=1;i<=n;i++){char ch[5];scanf("%s",ch);if(ch[0]=='t'){hao[i]=1;hao[i+n]=1;}else{hao[i]=0;hao[i+n]=0;}num[i]=gi();num[i+n]=num[i];}for(int k=1;k<=2*n;k++)for(int i=1;i<=2*n;i++){f[k][i][i]=num[i];g[k][i][i]=num[i];}for(int x=1;x<=n;x++){int begin=x,end=begin+n-1;for(int i=end;i>=begin;i--)for(int j=i+1;j<=end;j++)for(int k=i;k<j;k++){int r1,r2;if(hao[k+1]){r1=f[x][i][k]+f[x][k+1][j];r2=g[x][i][k]+g[x][k+1][j];}else{r1=f[x][i][k]*f[x][k+1][j];r2=g[x][i][k]*g[x][k+1][j];}if(r1>f[x][i][j])f[x][i][j]=r1;if(r2>f[x][i][j])f[x][i][j]=r2;if(r1<g[x][i][j])g[x][i][j]=r1;if(r2<g[x][i][j])g[x][i][j]=r2;}}int maxn=-2e8;int que[51];int s=0;for(int i=1;i<=n;i++){if(f[i][i][i+n-1]==maxn){que[++s]=i;}if(f[i][i][i+n-1]>maxn){maxn=f[i][i][i+n-1];s=1;que[s]=i;}}printf("%d\n",maxn);for(int i=1;i<=s;i++)printf("%d ",que[i]);return 0; }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/gshdyjz/p/7444788.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的多边形游戏 DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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