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

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條評論
主站蜘蛛池模板: 国产成人小视频 | 美国一级毛片aa | 国产精品国产精品 | 欧美成人精品久久精品 | 久久精品久久久久 | 真实的国产乱xxxx在线播放 | 天天天天躁天天天天碰 | 麻豆久久婷婷综合五月国产 | 久久这里只有 | 黄色不良视频 | 亚洲精品一二三区-久久 | 伊人久久精品线影院 | 欧美日韩亚洲一区 | 国产亚洲精品国产 | 欧美做爱毛片 | 精品久久久久久久久久久久久久久 | 日韩欧美福利 | 欧美日韩国产一区二区三区 | 亚洲国内自拍愉拍20页 | 日韩欧美亚洲一区精选 | 久久久国产麻豆 | 男女一级做片a性视频 | 久久精品国产6699国产精 | 国产成人青青热久免费精品 | 日韩每日更新 | 日韩国产一区二区 | 精品一区二区三区免费毛片爱 | 中文字幕1区2区 | 国产亚洲欧洲国产综合一区 | 国产欧美一区二区三区精品 | 四虎视频国产精品免费入口 | 国产精品麻豆99久久 | 一级一级一级一级毛片 | 奇米在线播放 | 欧美深夜影院 | 国内精品久久久久影院日本 | 国产1区2区3区在线观看 | 午夜影视在线 | 久久riav.com | 特级毛片免费视频播放 | 中文字幕日韩精品一区口 |