POJ 1141 经典DP 轨迹打印

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

又几天没写博客了，大二的生活实在好忙碌啊，开了五门专业课，每周都是实验啊实验啊实验啊。。。。我说要本月刷够60题，但好像完不成了，也就每天1题的样子。如今写动规还是挺有条理的，包括这道需要打印轨迹，其实就是在POJ 2955的基础上进行下修改，记录下动规的方向，再用递归逆向输出即可！

是个区间DP，如果括号i和括号k匹配了，则 dp[i][j]=max(dp[i][j],dp[i][k]+1+dp[k+1][j])这个转移方程挺重要的，我一开始就是这个方程没写好。。弄得思路混乱了

还有就是一开始不知道为什么总是OLE，说我输出太多，我看了下POJ的discuss，说这道题的数据里面有一些空行或者乱字符，要用gets读取字符串，不能用scanf。果然AC

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <map>

using namespace std;

map<char,int> mp;

bool vis[];

void init()

{

    mp.insert(pair<char,int>('(',));

    mp.insert(pair<char,int>(')',-));

    mp.insert(pair<char,int>('[',));

    mp.insert(pair<char,int>(']',-));

}

char ch[];

int dp[][];

int dir[][];

void putdown(int x)

{

    if (ch[x]=='(' || ch[x]==')')

        printf("()");

    else

        printf("[]");

}

void print(int l,int r)

{

    if (l==r && dir[l][r]==-){

        putdown(l);

        return;

    }

    if (dir[l][r]==- ||l>r) return;

    if (dir[l][r]==-)

    {

        print(l,r-);

        putdown(r);

        return;

    }

    if (dir[l][r]==-)

    {

        putdown(l);

        print(l+,r);

        return;

    }

    printf("%c",ch[l]);

    print(l+,dir[l][r]-);

    printf("%c",ch[dir[l][r]]);

    print(dir[l][r]+,r);

}

int main()

{

    init();

    while (gets(ch))

    {

        if(ch[]=='e') break;

        int i,j,k,len;

        len=strlen(ch);

        memset(dp,,sizeof dp);

        memset(vis,,sizeof vis);

        memset(dir,-,sizeof dir);

        for (k=;k<len;k++)

        {

            for (i=;i<len-k;i++)

            {

                int p=i+k;

                int temp=dp[i][p];

                if (temp<=dp[i][p-]){

                    temp=dp[i][p-];

                    dir[i][p]=-;

                }

                if (temp<dp[i+][p]){

                    temp=dp[i+][p];

                    dir[i][p]=-;

                }

                dp[i][p]=temp;

                for (j=i+;j<=p;j++)

                {

                    if (mp[ch[i]]==-mp[ch[j]] && mp[ch[i]]>)

                    {

                        if (dp[i][p]<dp[i+][j-]++dp[j+][p])

                        {

                            dp[i][p]=dp[i+][j-]++dp[j+][p];

                            dir[i][p]=j;

                        }

                    }

                }

            }

        }

        print(,len-);

        putchar('\n');

    }

    return ;

}