正題

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】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。