POJ-1179 Polygon

妖狐艹你老母 2021-11-01 14:46 225阅读 0赞

**链接**：[http://poj.org/problem?id=1179][http_poj.org_problem_id_1179]

**题意**：开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“\*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：

1.选择一条边E以及由E连接着的2个顶点V1和V2；  
2.用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。  
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。要求求出游戏得分的最大值以及获得该最大值时第一步删除的边的编号。  
**思路**：区间dp裸题，枚举要删除的第一条边，在这种情况下用区间dp求出能获得的最大值，与[经典题石子合并][Link 1]不同，这道题的区间操作不止是相加，还有相乘，最大值有可能是通过两个负数相乘得来的，所以要记录最大值最小值，共有七种情况，写在代码里了（评论区哀嚎一片

**代码：**请忽略最上面的大佛（因为毫无用处

1 //
      2 //                       _oo0oo_
      3 //                      o8888888o
      4 //                      88" . "88
      5 //                      (| -_- |)
      6 //                      0\  =  /0
      7 //                    ___/`---'\___
      8 //                  .' \\|     |// '.
      9 //                 / \\|||  :  |||// \
     10 //                / _||||| -:- |||||- \
     11 //               |   | \\\  -  /// |   |
     12 //               | \_|  ''\---/''  |_/ |
     13 //               \  .-\__  '-'  ___/-. /
     14 //             ___'. .'  /--.--\  `. .'___
     15 //          ."" '<  `.___\_<|>_/___.' >' "".
     16 //         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     17 //         \  \ `_.   \_ __\ /__ _/   .-` /  /
     18 //     =====`-.____`.___ \_____/___.-`___.-'=====
     19 //                       `=---='
     20 //
     21 //
     22 //     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     23 //
     24 //               佛祖保佑         永无BUG
     25 //
     26 //
     27 //
     28  
     29 // #include<bits/stdc++.h>
     30 #include<iostream>
     31 #include<cstdio>
     32 #include<cmath>
     33 #include<string>
     34 #include<vector>
     35 #include<algorithm>
     36 #include<queue>
     37 #include<deque>
     38 #include<stack>
     39 #include<map>
     40 #include<cstring>
     41 
     42 #define inf 0x3f3f3f3f
     43 using namespace std;
     44  
     45 typedef long long ll;
     46 typedef long double ld;
     47  
     48 const int M = int(1e5)*3 + 5;
     49 const int mod = 10056;
     50  
     51 inline int lowbit(int x) {
     52     return x & (-x);
     53 }
     54 
     55 //op==1
     56 //++ ->+
     57 //maxn[l][r]=max(maxn[l][r],maxn[l][k-1]*maxn[k][r])
     58 //-- ->+
     59 //maxn[l][r]=max(maxn[l][r],minn[l][k-1]*minn[k][r])
     60 //++ ->+
     61 //minn[l][r]=min(minn[l][r],minn[l][k-1]*minn[k][r])
     62 //+- ->-
     63 //minn[l][r]=min(minn[l][r],minn[l][k-1]*minn[k][r])
     64 //+- ->-
     65 //minn[l][r]=min(minn[l][r],maxn[l][k-1]*minn[k][r])
     66 
     67 //op==0
     68 //++ ->+
     69 //maxn[l][r]=max(maxn[l][r],maxn[l][k-1]*maxn[k][r])
     70 //-- ->+
     71 //minn[l][r]=min(minn[l][r],minn[l][k-1]*minn[k][r])
     72 
     73 int maxn[105][105];
     74 int minn[105][105];
     75 int a[M];
     76 int op[M];
     77 int ans,cnt;
     78 int pos[M];
     79 int n;
     80 
     81 int dp(int x){
     82     memset(maxn,-inf,sizeof(maxn));
     83     memset(minn,inf,sizeof(minn));
     84     for(int i=x;i<=x+n-1;i++) minn[i][i]=maxn[i][i]=a[i];
     85 
     86     for(int len=1;len<=n;len++){
     87         for(int l=x;l<=x+n-len;l++){
     88             int r=l+len-1;
     89             for(int k=l+1;k<=r;k++){
     90                 if(op[k]==1){
     91                     maxn[l][r]=max(maxn[l][r],maxn[l][k-1]*maxn[k][r]);
     92                     maxn[l][r]=max(maxn[l][r],minn[l][k-1]*minn[k][r]);
     93                     minn[l][r]=min(minn[l][r],minn[l][k-1]*maxn[k][r]);
     94                     minn[l][r]=min(minn[l][r],minn[l][k-1]*minn[k][r]);
     95                     minn[l][r]=min(minn[l][r],maxn[l][k-1]*minn[k][r]);
     96                 }
     97                 else{
     98                     maxn[l][r]=max(maxn[l][r],maxn[l][k-1]+maxn[k][r]);
     99                     minn[l][r]=min(minn[l][r],minn[l][k-1]+minn[k][r]);
    100                 }
    101             }
    102         }
    103     }
    104 
    105     return maxn[x][x+n-1];
    106 }
    107 
    108 int main()
    109 {
    110     cnt=0;
    111     cin>>n;
    112     for(int i=1;i<=n;i++){
    113         char c;
    114         cin>>c>>a[i];
    115         a[i+n]=a[i];
    116         if(c=='x') op[i]=op[i+n]=1;
    117         else op[i]=op[i+n]=0;
    118     }
    119 
    120     for(int i=1;i<=n;i++){          //枚举删哪条边
    121         int tem=dp(i);
    122         if(tem==ans){
    123             pos[++cnt]=i;//这里不太明白为什么从0开始计数就WA了，可能是大佛不喜欢0
    124         }
    125         else if(tem>ans){
    126             ans=tem;
    127             pos[1]=i;
    128             cnt=1;
    129         }
    130     }
    131 
    132     cout<<ans<<endl;
    133     for(int i=1;i<=cnt;i++){
    134         if(i==cnt) cout<<pos[i]<<endl;
    135         else cout<<pos[i]<<" ";
    136     }
    137 
    138     return 0;
    139 }

**备注**：想了好长时间，最后才悟出来是个裸题

转载于:https://www.cnblogs.com/harutomimori/p/11287322.html

[http_poj.org_problem_id_1179]: http://poj.org/problem?id=1179
[Link 1]: https://www.cnblogs.com/harutomimori/p/11288549.html