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

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條評論
主站蜘蛛池模板: 国产精品麻豆99久久 | 国产一级做a爱片久久毛片a | 四虎4444hu4影视最新地址 | 视频一区在线 | 99视频在线看观免费 | 欧美另类精品 | 色婷婷亚洲十月十月色天 | 久久ww| 四虎澳门永久8848在线影院 | 男人的网站在线观看 | 国产日韩欧美精品一区二区三区 | 996热精品视频在线观看 | 天天综合色天天综合网 | 澳门成人免费永久视频 | 成人精品视频一区二区三区 | 五月天亚洲 | 综合网视频 | 国产永久视频 | 夜夜爱夜夜爽 | 97av在线| 久久99精品视免费看 | 亚洲视频区 | 亚洲国产欧美在线不卡中文 | 亚洲一区二区三区高清不卡 | 日韩免费高清一级毛片久久 | 日本一级特黄毛片免费视频 | 婷婷丁香亚洲 | 操美女免费看 | 成人亚洲国产 | 一区二区三区在线播放 | 91香蕉福利一区二区三区 | 国内精品伊人久久久久7777人 | 久久一级 | 国产精品视频成人 | 国产欧美久久一区二区 | 9i9精品国产免费久久 | 99r视频 | 玖玖中文| 亚洲精品高清在线一区二区三区 | 深夜福利视频网址 | 日韩高清在线播放不卡 |