#include#include#include#include#include#include#include#defineLLlonglong" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

poj 1141 Brackets Sequence

系統(tǒng) 2048 0

http://poj.org/problem?id=1141

著題的難點不在于動態(tài)規(guī)劃 而在于輸出

其實想想也不難 DP 后根據(jù)最優(yōu)解進行遞歸找需要匹配的括號就可以了

代碼及其注釋:

      #include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<map>

#include<queue>

#include<cmath>

#define LL long long



using namespace std;



const int N=105;

char s[N];

int mm[N][N];//l到r所需最少匹配

bool add[N];//是否需要匹配

int dp(int l,int r)

{

    if(l>r)

    return 0;

    if(mm[l][r]!=-1)

    return mm[l][r];

    if(l==r)//只有一個括號 必須匹配

    {

        mm[l][r]=1;

        return mm[l][r];

    }

    if(l<r)//找最優(yōu)

    {

        mm[l][r]=N;

        if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))

        {

             mm[l][r]=dp(l+1,r-1);

        }

        for(int i=l;i<r;++i)

        {

            mm[l][r]=min(mm[l][r],dp(l,i)+dp(i+1,r));

        }

        return mm[l][r];

    }

    return mm[l][r];

}

void findadd(int l,int r)//找符合條件的最優(yōu)向下遞歸 找需要匹配的括號

{

    if(l>r)

    return ;

    if(l==r)

    add[l]=true;

    if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))

    {

        if((l>r&&mm[l][r]==0)||mm[l][r]==mm[l+1][r-1])

        {

            findadd(l+1,r-1);

            return;

        }

    }

    for(int i=l;i<r;++i)

    {

        if(mm[l][i]+mm[i+1][r]==mm[l][r])

        {

            findadd(l,i);

            findadd(i+1,r);

            return ;

        }

    }



}

int main()

{

    while(gets(s))

    {

        int n=strlen(s);

        memset(mm,-1,sizeof(mm));

        memset(add,false,sizeof(add));

        dp(0,n-1);

        findadd(0,n-1);

        for(int i=0;i<n;++i)

        {

            if(add[i])

            {

                if(s[i]=='(')

                printf("%c)",s[i]);

                if(s[i]==')')

                printf("(%c",s[i]);

                if(s[i]=='[')

                printf("%c]",s[i]);

                if(s[i]==']')

                printf("[%c",s[i]);

                continue;

            }

            printf("%c",s[i]);

        }

        printf("\n");

    }

    return 0;

}


    

?

poj 1141 Brackets Sequence


更多文章、技術交流、商務合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 欧美 日韩 中文 | 在线 中文字幕 日韩 欧美 | 欧美成人高清视频 | 狠狠色噜噜噜噜狠狠狠狠狠狠奇米 | 欧美亚洲国产一区 | 日韩欧美亚洲国产精品字幕久久久 | 四虎在线视频免费观看 | 国产成人黄网址在线视频 | 毛片日韩| 亚洲成人一区二区 | 色偷偷在线刺激免费视频 | 欧美精品亚洲精品日韩 | 就草草在线观看视频 | 精品国产综合区久久久久99 | 欧美成人久久一级c片免费 欧美成人剧情中文字幕 | 日本熟hd| 91精品国产爱久久久久久 | 国产精品久久久久久久久鸭 | 七七七久久久久人综合 | 国产99久久久久久免费看 | 精品午夜寂寞黄网站在线 | 国产亚洲精品xxx | 九色九色九色在线综合888 | 图片专区亚洲 欧美 另类 | 国产性大片黄在线观看在线放 | 91精品国产免费 | 久久97久久 | 亚洲在线视频免费 | 成人午夜性a一级毛片美女 成人午夜性视频欧美成人 成人午夜亚洲影视在线观看 | 99久久国产综合精品2020 | 久久国产精品高清一区二区三区 | a网站在线观看 | 亚洲国产人成中文幕一级二级 | 久久亚洲精品中文字幕第一区 | 国内精品久久久久久久久久影视 | 国产在线不卡视频 | 色妞ww精品视频7777 | 久久国产视频一区 | 91在线免费公开视频 | 欧美一级级毛片 | 视频一区精品 |