精华内容
下载资源
问答
  • 动态规划-多边形游戏问题
    2021-05-23 04:20:41

    1.描述:有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。

    游戏第1步,将一条边删除。

    随后n-1步按以下方式操作:

    (1)选择一条边E以及由E连接着的2个顶点V1和V2;

    (2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。

    最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。

    输入:

    输入共两行,第一行一个整数n表示顶点个数,第二行共2*n个数,分别为数字和字符。

    例如:对于上图中的问题,我们可以这样按输入样例中的例子输入,数学中的“+”号代表加法,小写字母“x”代表乘法。

    输出:

    一个整数,计算最高得分。

    输入样例:

    5

    10 + -1 x -2 x 3 + -8 x

    输出样例:

    486

    2.问题分析

    解决该问题可用动态规划中的最优子结构性质来解。

    设所给的多边形的顶点和边的顺时针序列为op[1],v[1],op[2],v[2],op[3],…,op[n],v[n] 其中,op[i]表示第i条边所对应的运算符,v[i]表示第i个顶点上的数值,i=1~n。

    在所给的多边形中,从顶点i(1<=i<=n)开始,长度为j(链中有j个顶点)的顺时针链p(i,j)可表示为v[i],op[i+1],…,v[i+j-1]。

    设m1是对子链p[i][s]的任意一种合并方式得到的值,而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p[i+s][j-s]的任意一种合并方式得到的值,而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有a≤m1≤b,c≤m2≤d

    (1)当op[i+s]=’+’时,显然有a+c≤m≤b+d

    (2)当op[i+s]=’*’时,有min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd}

    换句话说,主链的最大值和最小值可由子链的最大值和最小值得到。例如,当m=ac时,最大主链由它的两条最小主链组成;同理当m=bd时,最大主链由它的两条最大子链组成。无论哪种情形发生,由主链的最优性均可推出子链的最优性。

    综上可知多边形游戏问题满足最优子结构的性质。

    3.递归求解

    由前面的分析可知,为了求链合并的最大值,必须同时求子链合并的最大值和最小值。因此,在整个计算过程中,应同时计算最大值和最小值。

    设m[i,j,0]是链p(i,j)合并的最小值,而m[i,j,1]是最大值。若最优合并在op[i+s]处将p(i,j)分为两个长度小于j的子链p(i,i+s)和p(i+s,j-s),且从顶点i开始的长度小于j的子链的最大值和最小值均已经计算处。为了叙述方便,记

    a=m[i,i+s,0]

    b=m[i,i+s,1]

    c=m[i+s,j-s,0]

    d=m[i+s,j-s,1]

    (1)当op[i+s]='+'时,

    m[i,j,0]=a+c

    m[i,j,1]=b+d

    (2)当op[i+s]='*'是,

    m[i,j,0]=min{ac,ad,bc,bd}

    m[i,j,1]=max{ac,ad,bc,bd}

    综合(1)和(2),将p(i,j)在op[i+s]处断开的最大值记为maxf(i,j,s),最小值记为minf(i,j,s),则

    a+c op[i+s]='+'

    minf(i,j,s)={

    min{ac,ad,bc,bd} op[i+s]='*'

    b+d op[i+s]='+'

    maxf(i,j,s)={

    max{ac,ad,bc,bd} op[i+s]='*'

    由于多边最优断开位置s有1≤s≤j-1的j-1种情况,由此可知

    m[i,j,0]=min{minf(i,j,s)} 1≤i,j≤n

    m[i,j,1]=max{maxf(i,j,s)} 1≤i,j≤n

    初始边界显然为

    m[i,j,0]=v[i] 1≤i≤n

    m[i,j,1]=v[i] 1≤ i≤n

    由于多边形是封闭的,在上面的计算中,当i+s>n是,顶点i+s实际编号为(i+s)mod n。按上述递推式计算出的m[i,n,1]即为首次删去第i条边后得到的最大得分。

    4.算法描述

    基于以上讨论可设计解多边形游戏问题的动态规划算法如下:

    void minMax(int i,int s,int j)

    { int e[5];

    int a=m[i][s][0],

    b=m[i][s][1],

    r=(i+s-1)%n+1,//妙!

    c=m[r][j-s][0],

    d=m[r][j-s][1];

    if(op[r]=='t')

    {minf=a+c;

    maxf=b+d;

    }

    else

    {

    e[1]=a*c;

    e[2]=a*d;

    e[3]=b*c;

    e[4]=b*d;

    minf=e[1];

    maxf=e[1];

    for(int k=2;k<5 kh>

    {if(minf>e[k]) minf=e[k];

    if(maxf

    }

    }

    }

    int polyMax(){

    for(int j=2;j<=n;j++)

    for(int i=1;i<=n;i++)

    for(int s=1;s

    {minMax(i,s,j);

    m[i][j][0]=100000;

    m[i][j][1]=-100000;

    if(m[i][j][0]>minf) m[i][j][0]=minf;

    if(m[i][j][1]

    }

    long int temp=m[1][n][1];

    for(int i=2;i<=n;i++)

    if(temp

    return temp;

    }

    【新方法】

    本题在处理顺时针循环时的下标时,有一个很妙的方法。即,

    r=(i+s-1)%n+1

    其实,本题从这样编纯属巧合。

    当i+s 并不需要减一的时候,用这种方法编就很方便。

    如果用传统的方法就是

    if(i==n) r=n;

    else r=i%n

    这样,以来r=(i+s-1)%n+1就简单了不少。

    【参考程序】

    #include

    #include

    long int minf,maxf,m[51][51][2];

    char op[52];

    int v[51],n;

    void in()

    {

    FILE *in=fopen("polygon2.in","r");

    fscanf(in,"%d",&n);

    fgetc(in);

    for(int i=1;i<=n;i++)

    fscanf(in,"%c %d ",&op[i],&v[i]);

    fclose(in);

    }

    void iniM()

    {

    for(int i=1;i<=n;i++)

    {m[i][1][0]=v[i];

    m[i][1][1]=v[i];

    }

    }

    void minMax(int i,int s,int j)

    {

    int e[5];

    int a=m[i][s][0],

    b=m[i][s][1],

    r=(i+s-1)%n+1,//妙!

    c=m[r][j-s][0],

    d=m[r][j-s][1];

    if(op[r]=='t')

    {minf=a+c;

    maxf=b+d;

    }

    else

    {

    e[1]=a*c;

    e[2]=a*d;

    e[3]=b*c;

    e[4]=b*d;

    minf=e[1];

    maxf=e[1];

    for(int k=2;k<5 kh>

    {if(minf>e[k]) minf=e[k];

    if(maxf

    }

    }

    }

    int polyMax()

    {

    for(int j=2;j<=n;j++)

    for(int i=1;i<=n;i++)

    for(int s=1;s

    {minMax(i,s,j);

    m[i][j][0]=100000;

    m[i][j][1]=-100000;

    if(m[i][j][0]>minf) m[i][j][0]=minf;

    if(m[i][j][1]

    }

    long int temp=m[1][n][1];

    for(int i=2;i<=n;i++)

    if(temp

    return temp;

    }

    int main()

    {

    in();

    iniM();

    long int max=polyMax();

    printf("%ld\n",max);

    system("pause");

    return 0;

    }

    更多相关内容
  • PolygonGame DP 多边形游戏可视化 使用js实现将经典的DP问题 多边形游戏进行可视化 帮助更好理解算法过程
  • 多边形游戏

    2017-04-25 14:45:58
    算法设计与分析>>这么课的动态规划中的多边形游戏PPT。内容详细,简单易懂,纯个人理解综合汇总之精华,比其他的资料要好
  • 《算法设计与分析》多边形游戏的实验代码及说明、实验报告等资料,需要者自取。
  • 多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符”+”或”*”。所有边依次用整数从1到n编号。 游戏第1步,将一条边删除。 随后n-1步按以下...
  • 动态规划-多边形游戏

    2018-11-08 11:52:58
    动态规划算法通常用于求解具有某种最优性质的问题.在这类问题中,可能会有...多边形游戏问题描述: 给定N个顶点的多边形,每个顶点标有一个整数,每条边上标有+(加)或是×(乘)号,并且N条边按照顺时针依次编号为1~N。
  • 多边形游戏算法

    2013-03-18 21:09:32
    实现多边形游戏算法,时间复杂度O(n^3),网上大多数此算法的代码有误,里面包含有测试样例。
  • c++实现多边形游戏

    2010-11-17 23:26:40
    标题: 多边形游戏 时 限: 1000 ms 内存限制: 10000 K 总时限: 3000 ms 描述: 多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”...
  • 多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步,将一条边删除。随后n-1步按以下方式...
  • 算法实验:多边形游戏问题

    千次阅读 2022-04-08 17:50:11
    解决多边形游戏问题

     源码置于文末,取用请点赞

    1、实验环境

    Visual C++ 6.0

    2、实验目的和要求

    一、实验目标:   利用动态规划实现多边形游戏。

    二、实验内容:

    • 给定N个顶点的多边形,每个顶点标有一个整数,每条边上标有+(加)或是×(乘)号,并且N条边按照顺时针依次编号为1~N。

    三、实验要求:

    • 给定一个多边形,顶点和边已进行标注。问:按照游戏规则,最高得分(最优值)是多少?对应该最高得分,按照什么顺序移走边(最优解)?

    3、解题思路、伪代码

    3.1解题思路

       设所给的多边形的顶点和边的顺时针序列为:op[1],v[1],op[2],v[2],...,op[n],v[n],其中op[i]表示第i条边所对应的运算符,v[i]表示第i个顶点上的数值(1<=i<=n)。从顶点i(1<=i<=n)开始,长度为j(链中有j个顶点)的顺时针链p(i,j)可表示为:v[i],op[i+1],...,v[i+j-1]。

      若这条链p(i,j)的最后一次合并运算在op[i+s](1<=s<=j-1)处,则在op[i+s]处将链分割为两个子链p(i,s)和p(i+s,j-s)。设m1是对子链p(i,s)的任意一种合并方式得到的值,a和b分别所有合并中的最小值和最大值;m2是p(i+s,j-1)的任意一种合并方式得到的值,c和d分别是所有合并中的最大值和最小值;故a<=m1<=b,c<=m2<=d。m=m1 op[i+s] m2是两条子链合并的值;当op[i+s]=’+’时,a+b<=m<=b+d;当op[i+s]=’*’时,由于v[i]可取负数,故min{ac,ad,bc,bd}<=m<=max{ac,ad,bc,bd};所以主链的最大和最小值可由子链的最大和最小值得到。

    作为一个封闭的多边形,删除了第一条边以后,需要从每个边处断开一次分成2个子链,这里就一定要每个都遍历一遍之后才可以得到最后的最大值。而且本实验由于负数和乘号的存在,使得在求最大值时需要分情况讨论。如果操作符为+的话,只需要两个链的最大值相加即可,如果操作符是x的话,那么必须把各种情况考虑进来,然后再求出最大值。

    3.2 伪代码

    int N,m[NMAX+1][NMAX+1][2],v[NMAX+1];

    char op[NMAX+1];

    main()

    {

    int p;

    print("请输入多边形顶点数:" );input(N);

    for (int i = 1; i <= N; i++)

    {

    print("请输入多边形顶点");input(v[i]);

    m[i][1][0] = v[i];

    m[i][1][1] = v[i];

    print("请输入多边形边");input(op[i]);

    }

    print("多边形游戏首次删除第"); PloyMax(N, p);

    }

    int PloyMax(int n, int& p)

    {

    int minf, maxf;

    for (int j = 2; j <= n; j++) //迭代链的长度(所含顶点数目)

    {

    for (int i = 1; i <= n; i++)//迭代首次删掉第i条边

    {

    for (int s = 1; s <= j - 1; s++) //迭代断开位置

    {

    MinMax(n, i, s, j, minf, maxf);

    if (m[i][j][0] > minf) m[i][j][0] = minf;

    if (m[i][j][1] < maxf) m[i][j][1] = maxf;

    }

    }

    }

    int temp = m[1][n][1];

    p = 1;

    for (int i = 2; i <= n; i++)

    {

    if (temp < m[i][n][1])

    {

    temp = m[i][n][1];

    p = i;

    }

    }

    return temp;

    }

    void MinMax(int n, int i, int s, int j, int &minf, int &maxf)

    {

    int e[5];

    int a = m[i][s][0], b = m[i][s][1];

    int r = (i + s - 1) % n + 1;//多边形的实际顶点编号

    int c = m[r][j - s][0], d = m[r][j - s][1];

    if (op[r - 1] == '+')

    {

    minf = a + c;

    maxf = b + d;

    }

    else

    {

    e[1] = a * c;

    e[2] = a * d;

    e[3] = b * c;

    e[4] = d * b;

    minf = e[1];

    maxf = e[1];

    for (int r = 2; r < N; r++)

    {

    if (minf > e[r])minf = e[r];

    if (maxf < e[r])maxf = e[r];

    }

    }

    }

    4、实验步骤

    4.1输入:

     

     

    4.2输出:

     

     源码:

    #include<stdio.h>
    #define maxnum 100
    #define Max 999999
    #define Min -999999
     
    int dp[maxnum*2][maxnum*2][2];					//dp[][][0]用于存储最大值,dp[][][1]用于存储最小值
    int val[maxnum];							//存储顶点值 
    char sign[maxnum];							//存储边上符号 
    char order[maxnum];							//存储各种情况下的最优删除顺序
    int ordord=0;
    int ord[maxnum];
     
    int countMax(int i,int k,int len,char c){			//用于计算最大值 
    	int max = Min,temp;
    	if(c=='+'){
    		return dp[i][k][0]+dp[k+1][i+len][0];
    	}
    	if(c=='*'){
    		temp = dp[i][k][0]*dp[k+1][i+len][0];
    		if(temp>max){
    			max = temp;
    		}
    		temp = dp[i][k][0]*dp[k+1][i+len][1];
    		if(temp>max){
    			max = temp;
    		}
    		temp = dp[i][k][1]*dp[k+1][i+len][1];
    		if(temp>max){
    			max = temp;
    		}
    		temp = dp[i][k][1]*dp[k+1][i+len][0];
    		if(temp>max){
    			max = temp;
    		}
    		return max;
    	}
    }
    int countMin(int i,int k,int len,char c){			//用于计算最小值 
    	int min = Max,temp;
    	if(c=='+'){
    		return dp[i][k][1]+dp[k+1][i+len][1];
    	}
    	if(c=='*'){
    		temp = dp[i][k][1]*dp[k+1][i+len][1];
    		if(temp<min){
    			min = temp;
    		}
    		temp = dp[i][k][0]*dp[k+1][i+len][0];
    		if(temp<min){
    			min = temp;
    		}
    		temp = dp[i][k][1]*dp[k+1][i+len][0];
    		if(temp<min){
    			min = temp;
    		}
    		temp = dp[i][k][0]*dp[k+1][i+len][1];
    		if(temp<min){
    			min = temp;
    		}
    		return min;
    	}
    }
     
    void getord(int maxline,int maxn,int n){
    	int flag=0;
    	int k;
    	int len = n-1;
    	if(maxline==maxline+n-1){
    		return;
    	}
    	else{
    		for(k=maxline;k<maxline+len;k++){
    			if(countMax(maxline,k,len,sign[k])==maxn){
    				order[ordord] = sign[k];
    				ord[ordord] = k;
    				ordord++;
    				break;
    			}
    		}
    		getord(maxline,dp[maxline][k][0],k-maxline+1);
    		getord(k+1,dp[k+1][maxline+n-1][0],maxline+n-1-k-1+1);
    	}
    }
     
    int main(){
    	int n;
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
    		scanf("%d",&val[i]);
    		scanf("%c",&sign[i]);
    		val[i+n] = val[i];
    		sign[i+n] = sign[i];
    	}
    	for(int i=0;i<2*n;i++){
    		dp[i][i][0] = val[i];
    		dp[i][i][1] = val[i];
    	}	
    	for(int len=1;len<n;len++){
    		for(int i=0;i<n;i++){
    			int max=Min,min=Max,tempmax,tempmin;
    			for(int k=i;k<i+len;k++){
    				tempmax = countMax(i,k,len,sign[k]);
    				tempmin = countMin(i,k,len,sign[k]);
    				if(tempmax>max){
    					max = tempmax;
    				}
    				if(tempmin<min){
    					min = tempmin;
    				}
    			}
    			dp[i][i+len][0] = max;
    			dp[i][i+len][1] = min;
    			if(i+len+n<2*n){
    				dp[i+n][i+n+len][0] = dp[i][i+len][0];
    				dp[i+n][i+n+len][1] = dp[i][i+len][1];
    			}
    		}
    	}
    	int maxline,maxn = Min;
    	for(int i=0;i<n;i++){
    		if(dp[i][i+n-1][0]>maxn){
    			maxn = dp[i][i+n-1][0];
    			maxline = i;
    		}
    	}
    	if(maxline==0){
    		printf("最优值为%d,删除%d号边得到\n",maxn,maxline+n);
    	}
    	else
    		printf("最优值为%d,删除%d号边得到\n",maxn,maxline);
    	getord(maxline,maxn,n);
    	printf("删除边的顺序为:"); 
    	for(int i=n-2;i>=0;i--){
    		printf("%c(%d)",order[i],ord[i]%n+1);
    	}
    } 

    展开全文
  • 算法:多边形游戏

    2019-10-31 20:13:02
    游戏规则 :(1) 首先,移走一条边。 (2) 然后进行下面的操作: 选中一条边E,该边有两个相邻的顶点,不妨称为V1和V2。对V1和V2顶点所标的整数按照E上所标运算符号(+或是×)进行运算,得到一个整数;用该整数标...

    1、问题描述:

      给定N个顶点的多边形,每个顶点标有一个整数,每条边上标有+(加)或是×(乘)号,并且N条边按照顺时针
    

    依次编号为1~N。下图给出了一个N=4个顶点的多边形。
    在这里插入图片描述
    游戏规则 :(1) 首先,移走一条边。 (2) 然后进行下面的操作: 选中一条边E,该边有两个相邻的顶点,不妨称为V1和V2。对V1和V2顶点所标的整数按照E上所标运算符号(+或是×)进行运算,得到一个整数;用该整数标注一个新顶点,该顶点代替V1和V2 。 持续进行此操作,直到最后没有边存在,即只剩下一个顶点。该顶点的整数称为此次游戏的得分(Score)。
    在这里插入图片描述
    2、问题分析:

     解决该问题可用动态规划中的最优子结构性质来解。
    
    设所给的多边形的顶点和边的顺时针序列为op[1],v[1],op[2],v[2],op[3],…,op[n],v[n] 其中,op[i]表示第i条边所对应的运算符,v[i]表示第i个顶点上的数值,i=1~n。
    

    在这里插入图片描述
    在所给的多边形中,从顶点i(1<=i<=n)开始,长度为j(链中有j个顶点)的顺时针链p(i,j)可表示为v[i],op[i+1],…,v[i+j-1],如果这条链的最后一次合并运算在op[i+s]处发生(1<=s<=j-1),则可在op[i+s]处将链分割为两个子链p(i,s)和p(i+s,j-s)。
    举例理解 p(i,s)和p(i+s,j-s)
    例如:
    在这里插入图片描述
    假如从op【4】处断开,(1+3=4),s=4,j=5,则剩p(1,3)和p(4,2)。

    设m[i,j,0]是链p(i,j)合并的最小值,而m[i,j,1]是最大值。若最优合并在op[i+s]处将p(i,j)分为两个长度小于j的子链的最大值和最小值均已计算出。即:

    a=m[i,s,0]  b=m[i,s,1]  c=m[i+s,j-s,0]  d=m[i+s,j-s,1]
    

    (1) 当op[i+s]=’+’时

    m[i,j,0]=a+c ;m[i,j,1]=b+d
    

    (2) 当op[i+s]=’*’时

    m[i,j,0]=min{ac,ad,bc,bd} 
    

    m[i,j,1]=max{ac,ad,bc,bd}

    由于最优断开位置s有1<=s<=j-1的j-1中情况。 初始边界值为:
    
     m[i,1,0]=v[i]   1<=i<=n 
    
     m[i,1,1]=v[i]   1<=i<=n
    
    因为多变形式封闭的,在上面的计算中,当i+s>n时,顶点i+s实际编号为(i+s)modn。按上述递推式计算出的m[i,n,1]记为游戏首次删除第i(1<=i<=n)条边后得到的最大得分。
    源代码:
    
    #include<bits/stdc++.h> 
    using namespace std;
     
    #define NMAX 100
    int N,m[NMAX+1][NMAX+1][2],v[NMAX+1];
    char op[NMAX+1];
     
    void MinMax(int n,int i,int s,int j,int &minf,int &maxf);
    int PloyMax(int n,int& p);
     
    int main()
    {
        int p;
        cout<<"请输入多边形顶点数:"<<endl;
        cin>>N;
        for(int i=1; i<=N; i++)
        {
            cout<<"请输入多边形顶点"<<i<<"数值:"<<endl;
            cin>>v[i];
            m[i][1][0]=v[i];
            m[i][1][1]=v[i];
            cout<<"请输入多边形边"<<i<<"运算符:"<<endl;
            cin>>op[i];
        }
        cout<<"多边形游戏首次删除第"<<p<<"条边,结果为:"<<PloyMax(N,p)<<endl;
        return 0;
    }
     
    void MinMax(int n,int i,int s,int j,int &minf,int &maxf)
    {
        int e[4];//用于存ac,ad,bc,bd 
        int a=m[i][s][0],b=m[i][s][1];
        int r=(i+s-1)%n+1;//多边形的实际顶点编号
        int c=m[r][j-s][0],d=m[r][j-s][1];
     
        if(op[r-1]=='+')
        {
            minf=a+c;
            maxf=b+d;
        }
        else
        {
            e[1]=a*c;
            e[2]=a*d;
            e[3]=b*c;
            e[4]=d*b;
            minf=e[1];
            maxf=e[1];//初始化 
     
            for(int r=2;r<N;r++)
            {
                if(minf>e[r])minf=e[r];
                if(maxf<e[r])maxf=e[r];
            }
        }
    }
     
    int PloyMax(int n,int& p)
    {
        int minf,maxf;
        for(int j=2;j<=n;j++) //迭代链的长度(所含顶点数目)
        {
            for(int i=1;i<=n;i++)//迭代首次删掉第i条边
            {
                for(int s=1 ;s<j;s++) //迭代断开位置
                {
                    MinMax(n,i,s,j,minf,maxf);
                    if(m[i][j][0]>minf) m[i][j][0]=minf;
                    if(m[i][j][1]<maxf) m[i][j][1]=maxf;
                }
            }
        }
     
        int temp=m[1][n][1];
        p=1;
     
        for(int i=2 ;i<=n; i++)
        {
            if(temp<m[i][n][1])
            {
                temp=m[i][n][1];
                p=i;
            }
        }
        return temp;
    }
    

    运行效果:
    在这里插入图片描述

    展开全文
  • 一、问题描述多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步,将一条边删除。随后n-1...

    一、问题描述

    多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。

    游戏第1步,将一条边删除。

    随后n-1步按以下方式操作:

    (1)选择一条边E以及由E连接着的2个顶点V1和V2;

    (2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。

    最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。

    问题:对于给定的多边形,计算最高得分。

    如下图:

    a1acba23744a21bc84d4a781fe4a72e5.png

    其实该问题与之前讨论过的凸多边形最优三角剖分问题是类似的,但二者的最优子结构性质却不同。多边形游戏问题的最优子结构性质更具有一般性。

    二、算法思路

    1、最优子结构性质

    设所给的多边形的顶点和边的顺时针序列为op[1],v[1],op[2],v[2],op[3],…,op[n],v[n] 其中,op[i]表示第i条边所对应的运算符,v[i]表示第i个顶点上的数值,i=1~n。

    在所给的多边形中,从顶点i(1<=i<=n)开始,长度为j(链中有j个顶点)的顺时针链p(i,j)可表示为v[i],op[i+1],…,v[i+j-1],如果这条链的最后一次合并运算在op[i+s]处发生(1<=s<=j-1),则可在op[i+s]处将链分割为两个子链p(i,s)和p(i+s,j-s)。

    设m[i,j,0]是链p(i,j)合并的最小值,而m[i,j,1]是最大值。若最优合并在op[i+s]处将p(i,j)分为两个长度小于j的子链的最大值和最小值均已计算出。即:

    a=m[i,s,0]  b=m[i,s,1]  c=m[i+s,j-s,0]  d=m[i+s,j-s,1]

    (1) 当op[i+s]=’+’时

    m[i,j,0]=a+c ;m[i,j,1]=b+d

    该链的最优性由子链的最优性决定,最大值对应于子链的最大值,最小值对应于子链的最小值。

    (2) 当op[i+s]=’*’时

    m[i,j,0]=min{ac,ad,bc,bd} ; m[i,j,1]=max{ac,ad,bc,bd}

    由于v[i]可能取负数,子链的最大值相乘未必能得到主链的最大值,但是注意到,主链的最大值和最小值可以由子链的最大最小值得到。

    由于最优断开位置s有1<=s<=j-1的j-1中情况。 初始边界值为 m[i,1,0]=v[i]   1<=i<=n m[i,1,1]=v[i]   1<=i<=n

    2、递归求解

    可以得到递归表达式,将p(i,j)在op[i+s]处断开的最大值记为maxf(i,j,s),最小值记为minf(i,j,s)则:

    5392bdfc2320e51ed402dfe5dfd22370.png

    因为多变形式封闭的,在上面的计算中,当i+s>n时,顶点i+s实际编号为(i+s)mod n。按上述递推式计算出的m[i,n,1]记为游戏首次删除第i条边后得到的最大得分。

    3、算法描述

    void MinMax(int n,int i,int s,int j,int &minf,int &maxf)

    {int e[5];int a=m[i][s][0],b=m[i][s][1];int r=(i+s-1)%n+1;//多边形的实际顶点编号

    int c=m[r][j-s][0],d=m[r][j-s][1];if(op[r]=='t')

    {

    minf=a+c;

    maxf=b+d;

    }else{

    e[1]=a*c;

    e[2]=a*d;

    e[3]=b*c;

    e[4]=d*b;

    minf=e[1];

    maxf=e[1];for(int r=2; r<5; r++)

    {if(minf>e[r])

    minf=e[r];if(maxf

    maxf=e[r];

    }

    }

    }int PloyMax(int n,int&p)

    {intminf,maxf;for(int j=2; j<=n; j++) //迭代链的长度

    {for(int i=1; i<=n; i++) //迭代首次删掉第i条边

    {for(int s=1 ; s

    {

    MinMax(n,i,s,j,minf,maxf);if(m[i][j][0]>minf)

    m[i][j][0]=minf;if(m[i][j][1]

    m[i][j][1]=maxf;

    }

    }

    }int temp=m[1][n][1];

    p=1;for(int i=2 ; i<=n; i++)

    {if(temp

    {

    temp=m[i][n][1];

    p=i;

    }

    }returntemp;

    }

    4、计算复杂性分析

    与凸多边形最优三角剖分问题类似,上述算法需要O(n3)计算时间。

    5、例题

    #include#include

    #define MAX 200

    #define INF 0x7fffffff

    using namespacestd;int m[MAX+1][MAX+1][2];int v[MAX+1];int out[MAX+1];char op[MAX+1];int ans=-INF;intminf,maxf;intn;void MinMax(int i,int s,intj)

    {int e[5];int a=m[i][s][0];int b=m[i][s][1];int r=(i+s-1)%n+1;//多边形的实际顶点编号

    int c=m[r][j-s][0];int d=m[r][j-s][1];if(op[r]=='t')

    {

    minf=a+c;

    maxf=b+d;

    }else{

    e[1]=a*c;

    e[2]=a*d;

    e[3]=b*c;

    e[4]=d*b;

    minf=e[1];

    maxf=e[1];for(int k=2; k<5; k++)

    {

    maxf=max(maxf,e[k]);

    minf=min(minf,e[k]);

    }

    }

    }intmain()

    {

    scanf("%d",&n);

    getchar();for(int i=1; i<=n; i++)

    {

    scanf("%c %d",&op[i],&v[i]);

    m[i][1][1]=v[i];

    m[i][1][0]=v[i];

    getchar();

    }for(int j=2; j<=n; j++)//迭代链的长度

    {for(int i=1; i<=n; i++) //迭代首次删掉的边

    {for(int s=1; s

    {

    MinMax(i,s,j);if(s==1)

    {

    m[i][j][0]=minf;

    m[i][j][1]=maxf;

    }else{

    m[i][j][1]=max(maxf,m[i][j][1]);

    m[i][j][0]=min(minf,m[i][j][0]);

    }

    }

    }

    }inti;int cnt=0;for(i=1; i<=n; i++)

    {if(m[i][n][1]>ans)

    {

    ans=m[i][n][1];

    }

    }for(i=1; i<=n; i++)

    {if(m[i][n][1]==ans)

    {

    cnt++;out[cnt]=i;

    }

    }

    printf("%d",ans);for(i=1; i

    {

    printf("%d",out[i]);

    }

    printf("%d",out[i]);return 0;

    }

    再附上几组数据,方便调试:

    5x2 x 3 t 1 t 7 x 4

    224

    4

    5x-3 t -1 t -7 t -4 x -2

    30

    1 5

    3t0 x 1 t -2

    0

    1

    30x1 t 1 x 1 t 1 t 1 x 1 x 1 x 1 x 1 x 1 x 1 t 1 t 1 x 1 t 1 x 1 x 1 t 1 x 1 x 1 t 1 x 1 x 1 x 1 x 1 x 1 t 1 x 1 x 1 x 1

    288

    1 3 6 7 8 9 10 11 14 16 17 19 20 22 23 24 25 26 28 29 30

    48x1 x 2 x 1 x -1 t 1 x -1 x -1 x 1 t 1 t -1 x 1 t 2 x 1 x 2 t 1 x 1 x -1 x -2 x 1 x 1 t 1 x 1 t 1 x 1 x 1 x 1 t 1 x 1 x 1 x 1 x 1 x 1 x 1 x -1 t 1 x 1 x -1 x -1 t 1 x 1 t 1 x 1 x 1 x -1 t 1 t -1 t -1 x 1

    23328

    45

    展开全文
  • 多边形游戏(DP)

    千次阅读 2021-11-05 19:56:39
    多边形游戏”是一款单人益智游戏。 游戏开始时,给定玩家一个具有 N 个顶点 N 条边(编号 1∼N)的多边形,如图 1 所示,其中 N=4。 每个顶点上写有一个整数,每个边上标有一个运算符 +(加号)或运算符 *(乘号)...
  • #include #define NUM 10 /*limit the number of input integers *//**************** LIST ****************//*为了缩减代码,这里符号和数据都用同一种数据结构存贮的,所以我在这里用0来代表+,1来代表* */typedef...
  • JAVA实现多边形游戏

    2020-06-26 21:26:59
    5、实验四多边形游戏 实验内容 按照要求输入多边形的边和顶点,游戏第一步: 删除一条边, 随后的n-1步按以下方式操作: 1)选择一条边E以及由E连接着的2个顶点v1和v2 2)用一个新的顶点取代边E以及由E连着的2个...
  • 动态规划实现多边形游戏(python)游戏介绍大体思路(受他人文章启发)代码例子 游戏介绍 给定N个顶点的多边形,每个顶点标有一个整数,每条边上标有+(加)或是×(乘)号,并且N条边按照顺时针依次编号为1~N。 给定一...
  • 世界上有许许多多的不可能,但是即使再不可能。合全人类的力量还能做不成吗 地球本身就是一个大的自然圈。而这些用具、房屋、衣物不都是人类一点点...本篇介绍一个多边形游戏算法,它也是一个动态规划的经典算法。 1...
  • 多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。 游戏第1步,将一条边删除。 随后n-1步按以下...
  • 多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。 游戏第1步,将一条边删除。 随后n-1步按以下...
  • 直到最后所有边都被删除,剩下一个顶点,顶点上的数就是多边形游戏得分。 问题分析 n边形我们可以看成是一个首尾相连的圆,当然就可以使用循环链表实现了,但是这样一来就太麻烦了。对于这个问题,当我们选中一个...
  • 多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。 游戏第1步,将一条边删除。 随后n-1步按以下...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,960
精华内容 7,184
关键字:

多边形游戏