在深圳找工作哪个网站好,cp网站建设,优设网免费素材,企业微信功能详细介绍题意#xff1a;多边形游戏是一个单人玩的游戏#xff0c;开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值#xff0c;每条边被赋予一个运算符“”或“*”。所有边依次用整数从1到n编号游戏第1步#xff0c;将一条边删除随后n-1步按以下方式操作(1)选择一条边… 题意多边形游戏是一个单人玩的游戏开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值每条边被赋予一个运算符“”或“*”。所有边依次用整数从1到n编号 游戏第1步将一条边删除 随后n-1步按以下方式操作 (1)选择一条边E以及由E连接着的2个顶点V1和V2 (2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点 最后所有边都被删除游戏结束。游戏的得分就是所剩顶点上的整数值 这道题很有意思也比较有难度是一个算式形式的动态规划和区间dp还是有一定联系的因为我们每次开始游戏时需要断开一条边之后就变成了一条链可以看做区间这样我们初步应该会想到f[l][r]来表示l到r合并后最大的价值。 但是这样就会有一个非常谜的问题最大值不仅是由最大值加和而来的它还可能是由两个最小值乘来的负负得正)这样题就没法做了所以这个子问题不满足无后效性只能另寻它法虽然说这个子问题不合适但是这离我们的正解也已经非常近了。 我们可以用f[l][r]表示l到r所能合成的最大值然后f1[l][r]表示l到r能合成的最小值。为什么这就能满足无后效性呢因为啊 1.一个最大值无非就是由两个最大值相加两个最大值相乘或者两个最小值相乘而得来的 2.一个最小值无非就是由两个最小值相加或两个最小值相乘或前一个最小值和后一个最大值相乘或后一个最小值和前一个最大值相乘而得来的 所以我们就能够依据上述关系写出状态转移方程这里就不给出了 这样呢我们就能够用区间dp的套路安排循环但是有一个巨大的问题我们需要枚举首先断掉那条边这样下来会很麻烦怎么办呢。在处理动态规划的环形问题时我们可以先把这个环断掉从任意位置断掉然后长度复制一条一模一样的链连接在其后这样我们就可以通过区间的移动来达成首先断一条边的操作因为区间每次向右移动一位都代表着把原来断的那条边接上在把现有的最左边这条边断掉这样就能达成一个。枚举先断哪条边的作用 于是这道题完美解决下面看代码 1 //怕你飞远去2 //怕你离我而去3 //更怕你永远停留在这里4 #includeiostream5 #includecstdio6 #includecstdlib7 #includecstring8 #includestring9 #includecmath
10 #includealgorithm
11 #includequeue
12 using namespace std;
13 const int MAXN125;
14 int f[MAXN][MAXN],f1[MAXN][MAXN],a[MAXN],n;//f[l][r]代表区间l到r所能合成的最大值f1[l][r]表示区间l到r所能合成的最小值
15 char b[MAXN];
16 int main()
17 {
18 scanf(%d,n);
19 memset(f,-0x3f,sizeof(f));//初始化
20 memset(f1,0x3f,sizeof(f1));//初始化
21 for(int i1;in;i){
22 getchar();
23 scanf(%c%d,b[i],a[i]);
24 b[in]b[i];a[in]a[i];//断开复制成一个两倍长度的链
25 }
26 for(int i1;i2*n;i){
27 f1[i][i]f[i][i]a[i];//初始化
28 }//区间Dp
29 for(int i2;in;i){//阶段区间的长度
30 for(int l1;ln*2-i1;l){//状态左端点
31 int rli-1;//状态右端点
32 for(int kl;kr;k){//决策嗯
33 if(b[k1]t){
34 f[l][r]max(f[l][r],f[l][k]f[k1][r]);//最大值由两个最大值相加而来
35 f1[l][r]min(f1[l][r],f1[l][k]f1[k1][r]);//最小值由两个最小值相加而来
36 }
37 else{
38 f[l][r]max(f[l][r],f[l][k]*f[k1][r]);//最大值由两个最大值相乘而来
39 f[l][r]max(f[l][r],f1[l][k]*f1[k1][r]);//最大值由两个最小值相乘而来
40 f1[l][r]min(f1[l][r],f1[l][k]*f1[k1][r]);//最小值由两个最小值相乘而来
41 f1[l][r]min(f1[l][r],f[l][k]*f1[k1][r]);//最小值由前一个最大值和后一个最小值相乘而来
42 f1[l][r]min(f1[l][r],f1[l][k]*f[k1][r]);//最小值由前一个最小值和后一个最大值相乘而来
43 }
44 }
45 }
46 }
47 int maxx-0x7fffffff;
48 for(int i1;in;i){
49 maxxmax(maxx,f[i][in-1]);
50 }
51 printf(%d,maxx);
52 puts();
53 for(int i1;in;i){
54 if(f[i][n-1i]maxx){//枚举寻找第一步最优策略有几个输出几个
55 printf(%d ,i);
56 }
57 }
58 puts();
59 return 0;
60 } View Code 转载于:https://www.cnblogs.com/Alan-Luo/articles/8723289.html
