题意翻译

题目可能有些许修改，但大意一致

多边形是一个玩家在一个有n个顶点的多边形上的游戏，如图所示，其中n＝4。每个顶点用整数标记，每个边用符号+（加）或符号*（乘积）标记。

第一步，删除其中一条边。随后每一步：

选择一条边连接的两个顶点V1和V2，用边上的运算符计算V1和V2得到的结果来替换这两个顶点。

游戏结束时，只有一个顶点，没有多余的边。

如图所示，玩家先移除编号为3的边。之后，玩家选择计算编号为1的边，然后计算编号为4的边，最后，计算编号为2的边。结果是0。

（翻译者友情提示：这里每条边的运算符旁边的数字为边的编号，不拿来计算）

编写一个程序，给定一个多边形，计算最高可能的分数。

输入格式

输入描述一个有n个顶点的多边形，它包含两行。第一行是数字n，为总边数。

第二行描述这个多边形，一共有2n个读入，每两个读入中第一个是字符，第二个是数字。

第一个字符为第一条边的计算符号(t代表相加，x代表相乘)，第二个代表顶点上的数字。首尾相连。

3 < = n < = 50

对于任何一系列的操作，顶点数字都在[-32768,32767]的范围内。

输出格式

第一行，输出最高的分数。在第二行，它必须写出所有可能的被清除后的边仍能得到最高得分的列表，必须严格递增。

输入输出样例

输入样例#1：

4

t -7 t 4 x 2 x 5

输出样例#1：

33

1 2
-------------------------------------------------------------------

这道题就用来练一下区间dp了
首先这是一个环状多边形，将其拆成链状处理

　　a[i+n]=a[i]; op[i+n]=op[i];//断链-> n*2

令 dp[l][r]表示以 l 为首项，以 r 为末项的链经过删边可以得到的最大值
然后，列出状态转移方程。这分为两部分：+和*

1.对于+,即op[i+1]=='t';

　　dp[l][r]=max(dp[l][k]+dp[k+1][r],dp[l][r]);


2.对于*，情况稍微复杂：因为负负得正，所以我们还需要在转移时记录下
最小值[绝对值最大]，用f[i][j]记录

　　dp[l][r]=max( dp[l][r], max(dp[l][k]*dp[k+1][r],f[l][k]*f[k+1][r]) );

　　f[l][r]=min( f[l][r], min(dp[l][k]*dp[k+1][r],f[l][k]*f[k+1][r]) );

还要对边界进行处理，
令a[i]为第i个的初始值，那么：

　　dp[i][i]=f[i][i]=a[i];

同时，我们要先预处理长度为2的区间的答案

　　if(op[i+1]=='t'）

　　dp[i][i+1]=f[i][i+1]=a[i]+a[i+1];

if(op[i+1]=='x')

dp[i][i+1]=f[i][i+1]=a[i]*a[i+1];

最后！！！输入的时候注意令人智熄的scanf！！！！！
（查错两小时
因为本题中字符和数字在一行中输入，所以
直接写scanf("%s%d",&op[i],&a[i]);会导致读到的是空格
所以要写成scanf("%d\n",&n); 和scanf("%s %d ",&op[i],&a[i]);
但是对于我来说，经常记不到的话，以后有同时输入字符和数字的时候，应该果断选择cin

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define N 120

 #define INF 0x7f7f7f7f

 #define ll long long

 using namespace std;

 ll f[N][N],dp[N][N];

 int n,a[N];

 char op[N];

 ll ans=;

 int main()

 {

     scanf("%d",&n);

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

     {

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

         cin>>op[i]>>a[i];

         a[i+n]=a[i]; op[i+n]=op[i];//断链-> n*2

     }

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

         for(int j=i;j<=n*;j++)

             f[i][j]=INF,dp[i][j]=-INF;

     for(int i=;i<=n*;i++)//预处len=2

     {

         if(op[i+]=='t')

             dp[i][i+]=f[i][i+]=a[i]+a[i+];

         if(op[i+]=='x')

             dp[i][i+]=f[i][i+]=a[i]*a[i+];

         dp[i][i]=f[i][i]=a[i];

     }

     for(int len=;len<=n;len++)

         for(int l=;l<=n*-len+;l++)

         {

             int r=l+len-;

             for(int k=l;k<r;k++)

             {

                 if(op[k+]=='t')

                 {

                     dp[l][r]=max(dp[l][k]+dp[k+][r],dp[l][r]);

                     f[l][r]=min(f[l][k]+f[k+][r],f[l][r]);

                 }

                 else//乘法可能有负负得正 故记录最大和最小值

                 {

                     dp[l][r]=max( dp[l][r], max(dp[l][k]*dp[k+][r],f[l][k]*f[k+][r]) );

                     f[l][r]=min( f[l][r], min(dp[l][k]*dp[k+][r],f[l][k]*f[k+][r]) );

                 }

             }

         }

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

         //cout<<dp[i][i+n-1]<<" ";

         ans=max(ans,dp[i][i+n-]);

     printf("%lld\n",ans);

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

         if(ans==dp[i][i+n-])

             printf("%d ",i);

     return ;

 }

 /*

  scanf("%d\n",&n);

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

  和

  scanf("%d",&n);

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

  */

ovo

巴特西

【IOI1998】Polygon 区间DP

题意翻译

题目可能有些许修改，但大意一致

输入格式

输出格式

输入输出样例

最新文章

热门文章