多边形游戏 DP

题目描述】

多边形游戏是一种在一个具有n个顶点的多边形上进行的游戏。每个顶点有个权值（整

数）。如图1是一个n=4对应多边形，每个顶点上都有一个整数，每条边都有一个运算符+或者*，所有边按从1到n进行编号。

游戏都首先移除一条边，接下来可以进行如下操作：

选择一条边E和与之相关联的点V1和V2，用一个新的点替换它们，新点上的整数为V1,V2上的整数用E上的操作符运算后的结果。

没有边时游戏结束，游戏得分就是最后剩下的那个顶点上的整数。

对于图1中的多边形，如果游戏者首先去掉3，然后依次去掉1、4、2，最后得分将是0。

请你写一个程序，对于给定的多边形，计算出可能得到的最高分，并列出第一步移除哪些边可以得到这个最高分。

【输入格式】

输入文件game.in共两行，第一行是一个正整数n(3<=n<=50)，表示多边形的边数。

接下来一行是这个多边形的描述，包含n条边和n个顶点，加号边用t表示，乘号边用x表示，顶点用顶点上标的整数表示，输入按照边的编号从1到n的顺序给出。

【输出格式】

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

第二行输出一些边的列表，只有第一步移除的边在这个列表中才可能得到最高分。每条边都用这个边上的编号表示，列表必须是升序的。

【输入样例】

4

t -7 t 4 x 2 x 5

【输出样例】

33

1 2

---

 

刚开始看到这道题，我就一直懵逼了，根本懒得写，所以没用想到我以前做过的叫 石子合并 的一题。

这题和那题很像，附上题解：

我们发现本题和石子合并很相似，则容易想到用f[i][j]表示区间[i,j]的最大值，但题目有一点不同是还要求首先删掉的边，所以状态多一维f[x][i][j]表示首先删掉x，合并区间[i,j]的最优解。则方程为f[x][i][j] = max(f[x][i][j],f[x][i][k] +或* f[x][k + 1][j] )

注意，我们所关心的最大值不仅会由两个大的正数相加或相乘得到，还可能会由两个小的负数相乘得到，所以我们还需要用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; // 负数乘负数可能更新最大值

if(t1<f)g=t1; // 负数乘正数可能更新最小值

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; }

 

 

 

转载于:https://www.cnblogs.com/gshdyjz/p/7444788.html

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的多边形游戏 DP的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。