您的位置: 首页  >  文章  >  动态规划法----多边形游戏问题

动态规划法----多边形游戏问题

分类: 文章 • 2023-10-16 23:40:53

https://blog.****.net/jarvischu/article/details/6007014


一、题目

     给出一个多边形，满足：

          1. 每个顶点是一个数值

          2. 每条边是一个符号

     我们将某个边断开，形成一条数值和符号组成的链，然后计算这条链的值。

          1· 可以选择任意一条边断开。

          2.求链的值时，可以不必按运算符的优先级顺序，任意选择先后

    题目的要求是得到最大的值

 

二、示例

 

动态规划法----多边形游戏问题

 

三、分析

      1. 如上图，我们将图的信息保存如下：

          顶点数：REAL_SIZE = 3

          顶点：v[3] = {1,2,3}

          边： op[3] = {'+','x','+'}

     

      2. 假如我们从 边i 断开，则形成了链

          v[i],op[i+1],v[i+1],op[i+2] .....v[i+s-1],op[s],v[i+s]...op[i-1],v[i-1]

 

          计算得到其最大值，题目要求的最大值，也就是分别将每个边断开后，能得到的每条链的最大值中的最大的。

 

      3. 为了计算方便，我们记：

          p[i,j] 表示从顶点i开始，包括j个顶点的链

          m[i,j,0]表示这条链的最小值

          m[i,j,1]表示这条链的最大值

          这样 i 从 0到REAL_SIZE 的所有 m[i,REAL_SIZE,1]中最大的就是题目要的结果

 

      4. 将p[i,j]在op[i+s]处断开，则形成两条链p[i,s],和p[i+s,j-s]

          得到p[i,s]和p[i+s,j-s]的最小值和最大值，就可以得到p[i,j]在s处断开的最大值最小值

          当s 从1开始到 j-1，分别得到 对应的断开方法的最值，从这些最值中选择最小和最大的作为m[i,j,0]和m[i,j,1]

 

四、代码如下

         

[cpp] view plain copy
  1. #include<stdio.h>  
  2.   
  3. //--------------------------预定义与全局变量------------------------------------  
  4. #define MAX_VETEX_SIZE 20                              //程序能接受的最大顶点数目  
  5.   
  6. int REAL_SIZE;                                         //程序中实际的顶点数目  
  7. int m[MAX_VETEX_SIZE][MAX_VETEX_SIZE+1][2];            //保存最大最小值(第二维表示链中顶点个数)  
  8. int v[MAX_VETEX_SIZE];                                 //顶点（数值）  
  9. char op[MAX_VETEX_SIZE];                               //边（符号）  
  10.    
  11.   
  12. //--------------------------初始化m数组-----------------------------------------  
  13. void init_m(){  
  14.     int i;  
  15.     for(i=0;i<REAL_SIZE;i++){  
  16.         m[i][1][0] = v[i];                             //链中只有一个顶点i  
  17.         m[i][1][1] = v[i];  
  18.     }  
  19. }  
  20.    
  21.   
  22. //-----------------------返回四个数中的最值---------------------------------------------  
  23. void getMin_Max(int n1,int n2,int n3,int n4,int* min,int* max){  
  24.                                                       //返回四个操作数中的最大最小值  
  25.     *min = (n1>n2)?((n2>n3)? (n3>n4? n4:n3):(n2>n4? n4:n2))  
  26.                   :((n1>n3)? (n3>n4? n4:n3):(n1>n4? n4:n1));  
  27.       
  28.     *max = (n1<n2)?((n2<n3)? (n3<n4? n4:n3):(n2<n4? n4:n2))  
  29.                   :((n1<n3)? (n3<n4? n4:n3):(n1<n4? n4:n1));  
  30. }  
  31.   
  32.   
  33. //-----------------------获取有断点的最大最小值--------------------------------------  
  34. void minMax(int i,int s,int j,int* minf,int* maxf){  
  35.                                                        //p[i,j]从s处断开的最大值maxf 与 最小值minf  
  36. //  int e[4];                                          //ac，ad，bc，bd 的值  
  37.     int a,b,c,d,r;  
  38.     a = m[i][s][0];                                    //a 保存从i 到 i+s顶点构成链的最小值  
  39.     b = m[i][s][1];  
  40.   
  41.     r = (i+s)%REAL_SIZE;  
  42.   
  43.     c = m[r][j-s][0];  
  44.     d = m[r][j-s][1];  
  45. //printf("i=%d; s=%d; j=%d; r=%d/n",i,s,j,r);  
  46.     if(op[r] == '+'){                                  //处理加号  
  47.         *minf = a+c;  
  48.         *maxf = b+d;  
  49.     }  
  50.     else{                                              //处理乘法  
  51.         getMin_Max(a*c,a*d,b*c,b*d,minf,maxf);         //获取ac，ad，bc，bd 的最大最小值  
  52.     }  
  53. }  
  54.   
  55. //------------------------------获取结果-------------------------------------------------  
  56. int Poly_Max(){  
  57.     int minf,maxf,temp;  
  58.     int i,j,s;  
  59.     for(j=2;j<=REAL_SIZE;j++){                         //控制每个链中的顶点个数  
  60.         for(i=0;i<REAL_SIZE;i++){                       //控制每个链中的顶点的起始位置  
  61.             for(s=1;s<j;s++){  
  62.                 minMax(i,s,j,&minf,&maxf);  
  63.                 if(m[i][j][0] > minf) m[i][j][0] = minf;  
  64.                 if(m[i][j][1] < maxf) m[i][j][1] = maxf;           
  65.             }  
  66.             //此时已经获得了从i到i+j的顶点所有s对应的值中最大和最小  
  67.         }  
  68.     }  
  69.   
  70.     //求所有长度为REAL_SIZE个顶点的链中，值最大的  
  71.     temp = 0;  
  72.     for(i=1;i<REAL_SIZE;i++){  
  73.         if(m[i][REAL_SIZE][1] > m[temp][REAL_SIZE][1]){  
  74.             temp = i;  
  75.         }  
  76.     }  
  77.   
  78.     return m[temp][REAL_SIZE][1];  
  79. }  
  80.   
  81.   
  82.   
  83. //---------------------------------主函数--------------------------------------------------  
  84. void main(){  
  85.     int i =0;  
  86.   
  87.     scanf("%d",&REAL_SIZE);                        //用户输入顶点数目  
  88.     for(i=REAL_SIZE-1;i>=0;i--){                   //顶点和边信息  
  89.         scanf("%d %c",&v[i],&op[i]);           //输入样例如下   
  90.     }                                          //3  
  91.                                                        //1 x 3 + 2 +  
  92.     init_m();  
  93.   
  94.         printf("%d/n",Poly_Max());                     //输出为 9  
  95. }  

 

 


相关推荐