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

LA 3516 - Exploring Pyramids

系統 2387 0

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1517

久違的樹形dp

dp[l][r] 表示在l到r之間字符串形成的子樹有多少種

然后要枚舉最左樹枝所到位置 假設是 i 那么從l+1到i-1 遞歸就是最左樹枝的種類 然后乘上剩下的部分

剩下的部分i到r相當是去掉了最左樹枝的又一個子樹,遞歸就可以

代碼:

      #include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>



#define ll long long

using namespace std;



const ll MOD= 1000000000;

const int N=305;

ll dp[N][N];

char s[N];

ll dfs(int l,int r)

{

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

    return dp[l][r];

    if(l>r)

    return (dp[l][r]=0);

    if(l==r)

    return (dp[l][r]=1);

    if(s[l]!=s[r])

    return (dp[l][r]=0);

    dp[l][r]=0;

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

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

    dp[l][r]=(dp[l][r]+dfs(l+1,i-1)*dfs(i,r))%MOD;

    return dp[l][r];

}

int main()

{

    //freopen("data.in","r",stdin);

    while(scanf("%s",s)!=EOF)

    {

        int n=strlen(s);

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

        cout<<dfs(0,n-1)<<endl;

    }

    return 0;

}


    

LA 3516 - Exploring Pyramids


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

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

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 伊人久久国产免费观看视频 | 欧美久久久久久久一区二区三区 | 欧美性猛交xxxxxxxx软件 | 四虎成人欧美精品在永久在线 | 愉拍自拍| 久久精品一区二区三区中文字幕 | 欧美日韩一级大片 | 成人毛片18岁女人毛片免费看 | 激情综合网婷婷 | 91福利一区二区在线观看 | 免费国产福利 | 性短视频在线观看免费不卡流畅 | 狠狠干夜夜爽 | 97国产在线视频 | 黄片毛片免费在线观看 | 欧美国产日韩在线播放 | 一区二区日本 | 成年女人视频免费免费看 | 欧美日韩亚洲一区二区 | 免费一级a毛片在线播出 | 久久青草精品一区二区三区 | 亚洲精品tv久久久久久久久 | 香蕉国产综合久久猫咪 | 中文字幕最新中文字幕中文字幕 | 香蕉久久网| 国产成人精品视频免费大全 | 久久99热66这里只有精品一 | 中文字幕欧美日韩 | 成人欧美日韩高清不卡 | 日韩欧美亚洲综合久久影院d3 | 丝袜三级 | 亚洲成 人a影院青久在线观看 | 五月综合激情久久婷婷 | 精品在线视频播放 | 成人观看视频 | 91久久国产成人免费观看资源 | 欧美成年黄网站色高清视频 | 97se狠狠狠狠狼亚洲综合网 | 久久国产毛片 | 国产成版人视频网站免费下 | 日韩专区亚洲精品欧美专区 |