poj掛了快兩天了。。

洛谷的今日運勢真的強，說能完成WA的題就能完成。。

咳咳，區間DP。

思路類似合并果子，不過在維護f[i][j] (i到j的最大值) 同時也要維護g[i][j] (i到j的最小值）

為什么呢？考慮把區間劈成左右兩個的一次轉移：
對于加法：
1.最大值顯然是左右的最大值之和 max+max
對于乘法：
1.最大值是左右區間最大值的乘積 max*max
2.以及最小值的乘積（負數情況) min*min

因此要同時維護一下最小值才行，具體做法：
對于加法：
1.最小值是左右最小值之和
對于乘法：
1.左右最小值的乘積
2.左最小值*右最大值
3.左最大值*右最小值

對于環的處理：斷開，復制一倍

手c數組真的很危險。。WA的原因是只初始化[0,n]的數組，[n+1,n*2]的沒管。

emacs默認的兩格縮進自己看還行，好像發上來效果很擠？

#include<iostream> #include<cstdio>using namespace std;const int MAXN=500; const int INF=1<<30; int n;char op[MAXN]; int f[MAXN][MAXN],g[MAXN][MAXN]; int main(){scanf("%d",&n);for(int i=0;i<=2*n;i++){//2*for(int j=0;j<=2*n;j++){//2*f[i][j]=-INF;g[i][j]=INF;}}for(int i=1;i<=n;i++){char s[5];scanf("%s%d",s,&f[i][i]); // cin>>op[i-1]>>f[i][i];g[i][i]=f[i][i];g[i+n][i+n]=f[i+n][i+n]=f[i][i];op[i+n-1]=op[i-1]=s[0];}op[n<<1]=op[0];for(int len=1;len<=n;len++){for(int i=1;i+len<=2*n;i++){//2*int j=i+len;for(int k=i;k<j;k++){if(op[k]=='t'){f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]);}else{f[i][j]=max(f[i][j],max(f[i][k]*f[k+1][j],g[i][k]*g[k+1][j]));g[i][j]=min(g[i][j],min(g[i][k]*g[k+1][j],min(g[i][k]*f[k+1][j],f[i][k]*g[k+1][j])));}}}}int mx=-INF;for(int i=1;i<=n;i++)mx=max(mx,f[i][i+n-1]);cout<<mx<<endl;for(int i=1;i<=n;i++){if(f[i][i+n-1]==mx)cout<<i<<" ";}return 0; }

轉載于:https://www.cnblogs.com/ghostcai/p/9247424.html

總結

以上是生活随笔為你收集整理的[LUOGU] P4342 [IOI1998]Polygon的全部內容，希望文章能夠幫你解決所遇到的問題。

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