poj.1179Polygon(区间DP)题解xiaodangao

题目链接：http://poj.org/problem?id=1179
题意：略
思路：通过上一个石子合并的区间DP问题给了我思路(不熟悉$or$没写过的同学可以去刷$Acwing.282$)，石子合并问题中两个相邻石子合并的$value$是$sum$，而本题的$value$是$A op B$，具体说一下DP方法，第一层枚举区间长度，就类似于一个定长小方块的移动，每次均把相邻的长度为$Len$的小方块中的答案处理，含义是指在这个区间内子问题的答案，然后就涉及到状态的转移，因为我们第一层枚举的是长度，所以在我们处理$Len = i$时，对于每一个$Len \in [1,i-1]$我们均得到了答案，对于$Len = i$我们从下标为1开始枚举，每次该区间的答案是由$f[1][k] op f[k+1][i+1-1] (k \in [1,i+1-1])$进行得到，区间补充不漏，值得补充的是最外层还要加一个偏移量，因为要枚举第一条删掉的边，这样复杂度为$O(n^4)$，进一步思考可以得到，创造一个长度为$2*Len$的数组，枚举的长度变为$2*Len$，枚举一遍便可以得到答案，复杂度为$O(n^3)$，以下是我$O(n^4)$的做法
$Coding:$

/*************************************************************************
    > File Name: 283.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
    > Created Time: 2021年03月15日 星期一 18时26分21秒
 ************************************************************************/

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 50+10;
int arr[N],op[N];
int f[N][N];
int v;
int n;
int cal(int i){
    return (v+i)%n;
}
int uf[N][N];
vector<int>ans;
void solve(){

    read(n);
    rep(i,0,n-1){
        char s[3];
        scanf("%s",s);
        read(arr[i]);
        if(s[0] == 't')op[i] = 1;
    }
    int mx = -999999;
    rep(dlt,0,n-1){
        v = dlt;
        memset(f,0xcf,sizeof f);
        memset(uf,0x3f,sizeof f);
        rep(i,1,n)f[cal(i)][cal(i)] = arr[cal(i)],uf[cal(i)][cal(i)] = arr[cal(i)];
        rep(lens,2,n){
            rep(t,0,n-lens){
                int j = t+lens-1;
                rep(k,t,j-1){
                    //f[cal(t)][cal(j)] = max(f[cal(t)][cal(j)],op[cal(k+1)] == 0?f[cal(t)][cal(k)]*f[cal(k+1)][cal(j)]:f[cal(t)][cal(k)] + f[cal(k+1)][cal(j)]);
                    int h = f[cal(t)][cal(j)],a = f[cal(t)][cal(k)],b = f[cal(k+1)][cal(j)],a1 = uf[cal(t)][cal(k)],b1 = uf[cal(k+1)][cal(j)];
                    int h2 = uf[cal(t)][cal(j)];
                    if(op[cal(k+1)] == 1){
                        h = max(h,a+b);
                        h2 = min(h2,a1 + b1);
                    }
                    else {
                        h = max(h,a*b);
                        h = max(h,a1*b);
                        h = max(h,a*b1);
                        h = max(h,a1*b1);
                        h2 = min(h2,a*b);
                        h2 = min(h2,a*b1);
                        h2 = min(h2,a1*b);
                        h2 = min(h2,a1*b1);
                    }
                    f[cal(t)][cal(j)] = h;
                    uf[cal(t)][cal(j)] = h2;
                }
            }
        }
        if(mx < f[cal(0)][cal(n-1)]){
            mx = f[cal(0)][cal(n-1)];
            ans.clear();
            ans.pb(dlt+1);
        }
        else if(mx == f[cal(0)][cal(n-1)]){
            mx = f[cal(0)][cal(n-1)];
            ans.pb(dlt+1);
        }
        //mx = max(mx,f[cal(0)][cal(n-1)]);
    }
    write(mx);
    pc('\n');
    rep(i,0,(int)ans.size()-1){
        int p = ans[i];
        write(p);
        if(ans.size()-1 == i)pc('\n');
        else pc(' ');
    }

}

signed main(){
    solve();
    return 0;
}

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章