【POJ1179】Polygon (动态规划 DP)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 28 日

多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。

游戏第1步,将一条边删除。

随后n-1步按以下方式操作:

(1)选择一条边E以及由E连接着的2个顶点V1和V2;

(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。

最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。

问题:对于给定的多边形,计算最高得分。分析:

• 在所给多边形中,从顶点i(1≤i≤n)开始,长度为j(链中有j个顶点)的顺时针链p(i,j) 可表示为v[i],op[i+1],…,v[i+j-1]。

• 如果这条链的最后一次合并运算在op[i+s]处发生(1≤s≤j-1),则可在op[i+s]处将链分割为2个子链p(i,s)和p(i+s,j-s)。

• 设m1是对子链p(i,s)的任意一种合并方式得到的值,而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s,j-s)的任意一种合并方式得到的值,而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有a≤m1≤b,c≤m2≤d

(1)当op[i+s]='+'时,显然有a+c≤m≤b+d

(2)当op[i+s]='*'时,有min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd}

换句话说,主链的最大值和最小值可由子链的最大值和最小值得到。

/* 
http://acm.pku.edu.cn/JudgeOnline/problem?id=1179 
枚举 + 分段DP 
枚举所有边来删除,然后从删除的边右侧的起始点开始分段DP,对于乘法 
由于可能负负得正,因此需要考虑所有min和max的组合情况 
(1)对于加法 
max[i][j] = max(max[i][j], max[i][k] + max[k+1][j]), i <= k < j 
min[i][j] = min(min[i][j], min[i][k] + min[k+1][j]), i <= k < j 
(2)对于乘法 
max[i][j] = max(max[i][j], min[i][k] * min[k + 1][j], min[i][k] * max[k + 1][j], 
max[i][k] * min[k + 1][j], max[i][k] * max[k + 1][j]), i <= k < j 
min[i][j] = min(min[i][j], min[i][k] * min[k + 1][j], min[i][k] * max[k + 1][j], 
max[i][k] * min[k + 1][j], max[i][k] * max[k + 1][j]), i <= k < j 
另外每次DP在分段时由于起始位置不一定0,所以要注意边界转换问题 
*/  
#include <iostream>  
#include <algorithm>  
using namespace std;  
#define maxlen 51  
#define maxnum 999999999  
#define minnum -999999999  
int operand[maxlen];//操作数  
char operat[maxlen];//操作符  
//resmax[i][j]i到j合并的最大值  
int resmax[maxlen][maxlen];  
//resmin[i][j]i到j合并的最小值  
int resmin[maxlen][maxlen];  
int ansmax;//存储临时最大结果  
bool dedge[maxlen];//最大结果所删掉的边  
int n,i,j,k,steplen,deledge;  
int tempmax,tempmin;  
//初始化  
void ini()  
{  
    for (i=0;i<n;i++)  
        for (j=0;j<n;j++)  
            if(i == j)   
                resmax[i][j] = resmin[i][j] = operand[i];  
            else{  
                resmax[i][j] = minnum;  
                resmin[i][j] = maxnum;  
            }  
}  
int main(){  
    freopen("1.txt","r",stdin);  
    cin>>n;  
    for (i=0;i<n;i++)  
        cin>>operat[i]>>operand[i];  
    ansmax=minnum;  
    //对每条边进行删除遍历  
    for (deledge=0;deledge<n;deledge++)  
    {  
        ini();  
        //对应所删边的步长  
        for (steplen=2;steplen<=n;steplen++)  
        {  
            //遍历对应步长的起始位置  
            for (i=deledge;i<=n+deledge-steplen;i++)  
            {  
                //对应的起始位置的终点位置  
                j=i+steplen-1;  
                //遍历断点K  
                for (k=i;k<j;k++)  
                {  
                    int kleftmax=resmax[i%n][k%n];  
                    int kleftmin=resmin[i%n][k%n];  
                    int krightmax=resmax[(k+1)%n][j%n];  
                    int krightmin=resmin[(k+1)%n][j%n];  
                    //根据操作符不同进行不懂的动态转移式  
                    if(operat[(k+1)%n]=='t'){  
                        tempmax=kleftmax+krightmax;  
                        tempmin=kleftmin+krightmin;  
                    }  
                    else{  
                        tempmax=max(max(kleftmax*krightmax,kleftmin*krightmin),  
                            max(kleftmin*krightmax,kleftmax*krightmin));  
                        tempmin=min(min(kleftmax*krightmax,kleftmin*krightmin),  
                            min(kleftmin*krightmax,kleftmax*krightmin));  
                    }  
                    resmax[i%n][j%n]=max(resmax[i%n][j%n],tempmax);  
                    resmin[i%n][j%n]=min(resmin[i%n][j%n],tempmin);  
                }  
            }  
        }  
        //如果最大值不同则刷新结果,相同则对应位置为真  
        if(resmax[deledge][(deledge+n-1)%n]>ansmax)  
        {  
            memset(dedge,0,sizeof(dedge));  
            ansmax=resmax[deledge][(deledge-1+n)%n];  
            dedge[deledge]=1;  
        }else if(resmax[deledge][(deledge-1+n)%n]==ansmax)  
            dedge[deledge]=1;  
    }  
    //输出结果  
    cout<<ansmax<<endl;  
    for (i=0;i<n;i++)  
        if(dedge[i]) cout<<i+1<<" ";  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期日, 2017 年 12 月 17 日