正题

POJ题目链接:http://poj.org/problem?id=1179
洛谷评测记录:https://www.luogu.org/recordnew/lists?uid=52918&pid=P4342

---

题目大意

一个数字环，每个数字之间有一个符号（++或××），开始时选择一条边断开，然后任意选择两个点合并，合并之后的权值是原版两边的点进行边符号操作的值。求最后一个值最大。

---

解题思路

将原环复制一遍放在末尾，然后用f0,l,rf0,l,r表示l∼rl∼r区间已经合并了的最小权值，然后用f1,l,rf1,l,r表示最大值，然后每次枚举4种方式（大×/+×/+小,小×/+×/+小,大×/+×/+大,小×/+×/+大），然后就正常区间dp就好了。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; int n,op[101],dp[2][101][101],ans; int main() {memset(dp[0],127/3,sizeof(dp[0]));memset(dp[1],-127/3,sizeof(dp[1]));scanf("%d\n",&n);for(int i=1;i<=n;i++){if(i==n) scanf("%c %d",&op[i],&dp[0][i][i]);else scanf("%c %d ",&op[i],&dp[0][i][i]);dp[1][i][i]=dp[0][i][i];if(i!=n){dp[0][i+n][i+n]=dp[1][i+n][i+n]=dp[0][i][i];op[i+n]=op[i];}}for(int i=2;i<=n;i++)for(int l=1;l<=2*n-i;l++){int r=l+i-1;for(int k=l;k<r;k++){for(int p1=0;p1<2;p1++)for(int p2=0;p2<2;p2++){int tmp=op[k+1]=='t'?dp[p1][l][k]+dp[p2][k+1][r]:dp[p1][l][k]*dp[p2][k+1][r];dp[0][l][r]=min(dp[0][l][r],tmp);dp[1][l][r]=max(dp[1][l][r],tmp);//动态转移}}}ans=-2147483647;for(int i=1;i<=n;i++) ans=max(ans,dp[1][i][i+n-1]);//计算答案printf("%d\n",ans);for(int i=1;i<=n;i++)if(dp[1][i][i+n-1]==ans)printf("%d ",i);//统计答案 } 创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的POJ1179,P4342-[IOI1998]Polygon【区间dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。