首页 > 代码库 > POJ 1179 Polygon 区间DP
POJ 1179 Polygon 区间DP
链接:http://poj.org/problem?id=1179
题意:给出一个多边形,多边形的每个顶点是一个数字,每条边是一个运算符号“+”或者“x"。要求的过程如下,手下移除一条边,即这条边不做运算。之后每次移除一条边,将其两边的数字进行对应边的运算,用得到的数字来替代原来的两个点。要求所有边都移除以后得到的最大的答案。
思路:典型的区间DP,在过程中每次操作的处理方式为dp_max[i][j]=dp[i][k]*dp[k+1][j],dp_max[i][j]=dp[i][k]+dp[k+1][j],要开两个数组同时记录[i,k]区间的最大值和最小值,因为两个负数相乘时也可能得到最大值。其中dp_max数组表示的是[i,j]区间内从第i个数开始顺时针操作中得到的最大值。这样dp[i][i-1]就是我们所要的所有操作完毕后得到的最大值。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stack> #include<vector> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) #define maxn 55 #define INF 1<<25 typedef long long ll; using namespace std; int cal[maxn][3]; int num[maxn]; int tot; int dp_max[maxn][maxn]; int dp_min[maxn][maxn]; int tt=0; int aa[maxn]; int init() { for(int i=0; i<tot; i++) for(int j=0; j<tot; j++) { if(i==j) dp_max[i][j]=dp_min[i][j]=num[i]; else { dp_max[i][j]=-INF; dp_min[i][j]=INF; } } } int dp(int i,int j) { for(int k=i; k!=j; k=(k+1)%tot) { if(dp_max[i][k]==-INF) dp(i,k); if(dp_max[(k+1)%tot][j]==-INF) dp((k+1)%tot,j); if(cal[(k+1)%tot][0]=='t') { dp_max[i][j]=max(dp_max[i][j],dp_max[i][k]+dp_max[(k+1)%tot][j]); dp_max[i][j]=max(dp_max[i][j],dp_min[i][k]+dp_min[(k+1)%tot][j]); dp_max[i][j]=max(dp_max[i][j],dp_min[i][k]+dp_max[(k+1)%tot][j]); dp_max[i][j]=max(dp_max[i][j],dp_max[i][k]+dp_min[(k+1)%tot][j]); dp_min[i][j]=min(dp_min[i][j],dp_min[i][k]+dp_min[(k+1)%tot][j]); dp_min[i][j]=min(dp_min[i][j],dp_min[i][k]+dp_max[(k+1)%tot][j]); dp_min[i][j]=min(dp_min[i][j],dp_max[i][k]+dp_min[(k+1)%tot][j]); dp_min[i][j]=min(dp_min[i][j],dp_max[i][k]+dp_max[(k+1)%tot][j]); } if(cal[(k+1)%tot][0]=='x') { dp_max[i][j]=max(dp_max[i][j],dp_max[i][k]*dp_max[(k+1)%tot][j]); dp_max[i][j]=max(dp_max[i][j],dp_min[i][k]*dp_min[(k+1)%tot][j]); dp_max[i][j]=max(dp_max[i][j],dp_min[i][k]*dp_max[(k+1)%tot][j]); dp_max[i][j]=max(dp_max[i][j],dp_max[i][k]*dp_min[(k+1)%tot][j]); dp_min[i][j]=min(dp_min[i][j],dp_min[i][k]*dp_min[(k+1)%tot][j]); dp_min[i][j]=min(dp_min[i][j],dp_min[i][k]*dp_max[(k+1)%tot][j]); dp_min[i][j]=min(dp_min[i][j],dp_max[i][k]*dp_min[(k+1)%tot][j]); dp_min[i][j]=min(dp_min[i][j],dp_max[i][k]*dp_max[(k+1)%tot][j]); } } } int main() { int ans=-INF; scanf("%d",&tot); for(int i=0; i<tot; i++) scanf("%s%d",cal[i],&num[i]); init(); for(int i=0; i<tot; i++) { dp(i,(i-1+tot)%tot); if(dp_max[i][(i-1+tot)%tot]>ans) { ans=dp_max[i][(i-1+tot)%tot]; tt=0; aa[tt]=i; } else if(dp_max[i][(i-1+tot)%tot]==ans) { aa[++tt]=i; } } printf("%d\n",ans); printf("%d",aa[0]+1); for(int i=1;i<=tt;i++) printf(" %d",aa[i]+1); printf("\n"); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。