POJ 1179 Polygon 기억화 dfs vs dp

제목: n(3<=n<=50)의 변형을 정하고 각 정점은 하나의 숫자이며 각 변형은 하나의 연산 +(t)/*(x)이다.지금 한 가지 게임을 진행합니다. 두 단계로 나뉘어집니다. 하나는 가장자리를 파괴하는 것입니다.2 남은 n개의 숫자와 n-1종의 연산에서 임의의 연산 순서를 정하고 최대치를 얻어 최대치와 삭제점에 대응하는 변의 번호를 구한다.연산 과정 숫자의 범위는 [-32768,32767]이다.문제풀이: 서로 다른 변을 삭제할 때 직면하는 상황이 다르기 때문에 먼저 삭제 변을 열거한다. 첫 번째 변의 번호가 0이라고 가정하면 0-n-1 정점, 두 번째 변의 번호가 1이고 연결된 것은 1-2 정점... dp[i][j][0](i<=j)는 [i,j] 폐구간이 시계 반대 방향으로 얻은 최대치, dp[i][j][1](i<=j)는 [i,j] 폐구간이 시계 반대 방향으로 얻은 최대치를 의미한다.dp 과정이 비교적 복잡하기 때문에, 나는 기억화 dfs로 처리한다.dp[i][j][k](i<=j, 0<=k<=1)의 최소값과 최대값을 기록해야 한다(최소값을 기록한 원인은 다음과 같다). 그리고 마지막 연산의 위치를 열거하여 현재의 최대값과 최소값을 업데이트해야 한다./*5t-1t-2x-2t-3t-2ans:255*/PS: 이 문제의 출력 형식은 매우 까다롭다. 답안 가장자리의 번호 사이에만 printf(");회pe, 모든 답안의 번호 뒤에 printf(");비로소 ac, 아... 기억화 dfs와 dp의 관계를 간단하게 말하자면 먼저 기억화 dfs와 dp는 같은 문제를 해결한다. 즉, 현재의 문제는 간자문제를 합쳐서 해결할 수 있다. 이른바 dp방정식이다.dp는 작은 문제->큰 문제의 방향으로 해결하는 과정이고 기억화 dfs는 큰 문제->작은 문제의 방향으로 해결하는 과정이다. 이렇게 하면 쉽게 볼 수 있다. dp의 과정은 명확한 dp방정식을 필요로 하고 dfs를 기억하는 과정은 dp방정식에 대한 개념이 그렇게 명확하지 않다(어...개 사람이 생각하기에) 값은 큰 문제의 자문제를 정확하게 인식하고 자문제에서 큰 문제를 해결하는 방법을 정확하게 얻으면 된다.만약에 dp방정식을 쉽게 쓸 수 있다면 dp가 비교적 좋다. 이렇게 하면 시간의 복잡도를 쉽게 예측할 수 있다. 만약에 큰 문제의 하위 문제에 대해 잘 알면 기억화 dfs는 쉽게 손에 넣을 수 있다.Sure 오리지널, 전재는 출처를 밝혀 주십시오.

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn = 52;
int dpmax[maxn][maxn][2],dpmin[maxn][maxn][2],num[maxn],edge[maxn];
bool vis[maxn][maxn][2];
int n;

inline int MAX(int a,int b)
{
    return a > b ? a : b;
}

inline int MIN(int a,int b)
{
    return a < b ? a : b;
}

void read()
{
    memset(vis,false,sizeof(vis));
    char str[3];
    for(int i=0;i<n;i++)
    {
        scanf("%s %d",str,&num[i]);
        if(str[0] == 't') edge[i] = 0;
        else edge[i] = 1;
    }
    return;
}

int dfs(int st,int to,int d)
{
    if(vis[st][to][d])
    {
        return dpmax[st][to][d];
    }
    if(st == to)
    {
        vis[st][to][d] = true;
        return dpmax[st][to][d] = dpmin[st][to][d] = num[st];
    }
    if(d == 0)
    {
        bool flag = false;
        int resma , resmi;
        for(int i=st;i<to;i++)
        {
            int le = dfs(st , i , 0);
            int ll = dpmin[st][i][0];
            int ri = dfs(i+1 , to , 0);
            int rr = dpmin[i+1][to][0];

            int addma = MAX(MAX(le + ri , le + rr) , MAX(ll + ri , ll + rr));
            int mulma = MAX(MAX(le * ri , le * rr) , MAX(ll * ri , ll * rr));

            int addmi = MIN(MIN(le + ri , le + rr) , MIN(ll + ri , ll + rr));
            int mulmi = MIN(MIN(le * ri , le * rr) , MIN(ll * ri , ll * rr));

            int tma = edge[i+1] ? mulma : addma;
            int tmi = edge[i+1] ? mulmi : addmi;
            if(flag == false)
            {
                flag = true;
                resma = tma;
                resmi = tmi;
            }
            else
            {
                resma = MAX(resma , tma);
                resmi = MIN(resmi , tmi);
            }
        }
        vis[st][to][d] = true;
        dpmin[st][to][d] = resmi;
        return dpmax[st][to][d] = resma;
    }
    else
    {
        bool flag = false;
        int resma , resmi , le , ri , ll , rr;
        for(int i=st;i != to;)
        {
            int j = (i - 1 + n) % n;
            if(i <= st)
            {
                le = dfs(i , st , 0);
                ll = dpmin[i][st][0];
            }
            else
            {
                le = dfs(st , i , 1);
                ll = dpmin[st][i][1];
            }

            if(j >= to)
            {
                ri = dfs(to , j , 0);
                rr = dpmin[to][j][0];
            }
            else
            {
                ri = dfs(j , to , 1);
                rr = dpmin[j][to][1];
            }
            int addma = MAX(MAX(le + ri , le + rr) , MAX(ll + ri , ll + rr));
            int mulma = MAX(MAX(le * ri , le * rr) , MAX(ll * ri , ll * rr));

            int addmi = MIN(MIN(le + ri , le + rr) , MIN(ll + ri , ll + rr));
            int mulmi = MIN(MIN(le * ri , le * rr) , MIN(ll * ri , ll * rr));

            int tma = edge[i] ? mulma : addma;
            int tmi = edge[i] ? mulmi : addmi;
            if(flag == false)
            {
                flag = true;
                resma = tma;
                resmi = tmi;
            }
            else
            {
                resma = MAX(resma , tma);
                resmi = MIN(resmi , tmi);
            }
            i = j;
        }
        vis[st][to][d] = true;
        dpmin[st][to][d] = resmi;
        return dpmax[st][to][d] = resma;
    }
}

void solve()
{
    int res = dfs(0 , n-1 , 0);
    for(int i=0;i<n-1;i++)
    {
        res = MAX(res , dfs(i , i+1 , 1));
    }
    printf("%d
",res);
    bool flag = false;
    if(dpmax[0][n-1][0] == res)
    {
        printf("1 ");
    }
    for(int i=0;i<n-1;i++)
    {
        if(dpmax[i][i+1][1] == res)
        {
            printf("%d ",i+2);
        }
    }
    printf("
");
    return;
}

int main()
{
    while(~scanf("%d",&n))
    {
        read();
        solve();
    }
    return 0;
}