给定一个由 N 个顶点构成的多边形, 每个顶点被赋予一个整数值, 而每条边则被赋予一个符号:+(加法运算) 或者 *(乘法运算), 所有边依次用整数 1 到 N 标识.
一个多边形的图形表示 首次移动, 允许将某条边删除; 接下来的每次顺序移动包括下面步骤:
1, 选出一条边 E, 以及由 E 联接的顶点 V1 和 V2;
2, 用一个新的顶点, 取代边 E 及其所联接的两个顶点 V1 和 V2. 新顶点要赋予新的值, 这个值是对 V1 和 V2, 做由 E 所指定的运算, 所得到的结果.
所有边都被删除后, 只剩下一个顶点, 游戏结束. 游戏的得分就是该顶点的数值.
任务: 编写一个程序, 对于任意给定的多边形, 计算可能的最高得分, 并且列举出所有的可以导致最高得分的被首次移动的边.
** 注意: 可以枚举删掉的边,
分别 dp 出最优方案输出, 容易出错是状态转移方程: 枚举分隔点 k, 当 p[k]=='*'时 fmax[i,j]=max{fmax[i][k]*fmax[k+1][j],fmin[i][k]*fmin[k+1][j]};
因为最小值可能是负数相乘为正可能更大. 复杂度为 O(n^4). 可以省掉一次枚举删边的过程,
将环拆成两个链, 然后 dp 到 2*n, 最后 ans=max{f[i][i+n-1],1<=i<=n}.
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- int f[120][120],a[120],d[120][120];
- char p[120][120];
- int main()
- {
- int n,ans=-0xfffffff;
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>p[i-1][i];
- p[i][i-1]=p[i-1][i];
- cin>>a[i];
- }
- p[n][1]=p[1][n]=p[1][0];
- for(int i=1;i<=n;i++)
- {
- p[i+n-1][i+n]=p[i-1][i];
- p[i+n][i+n-1]=p[i+n-1][i+n];
- a[i+n]=a[i];
- }
- memset(d,0x3f,sizeof(d));
- memset(f,128,sizeof(f));
- for(int i=1;i<=2*n;i++)f[i][i]=d[i][i]=a[i];
- for(int l=1;l<=n;l++)
- for(int i=1;i<=2*n-l+1;i++)
- {
- int j=i+l-1;
- for(int k=i;k<j;k++)
- {
- if(p[k][k+1]=='t')
- {
- f[i][j]=max(f[i][k]+f[k+1][j],f[i][j]);
- d[i][j]=min(d[i][k]+d[k+1][j],d[i][j]);
- }
- if(p[k][k+1]=='x')
- {
- f[i][j]=max(max(f[i][k]*f[k+1][j],
- d[i][k]*d[k+1][j]),f[i][j]);
- d[i][j]=min(min(f[i][k]*d[k+1][j],
- d[i][k]*f[k+1][j]),min(f[i][k]*f[k+1][j],d[i][j]));
- }
- }
- }
- // cout<<f[1][n]<<endl;
- // for(int i=1;i<=2*n;i++)
- // { for(int j=1;j<=2*n;j++)
- //
- // cout<<f[i][j]<<" ";
- // cout<<endl;}
- for(int i=1;i<=n;i++)
- if(f[i][i+n-1]>ans)
- ans=f[i][i+n-1];
- cout<<ans<<endl;
- for(int i=1;i<=n;i++)
- if(f[i][i+n-1]==ans)
- cout<<i<<" ";
- }
来源: http://www.bubuko.com/infodetail-3101372.html