2019牛客多校第一场E ABBA（DP）题解-白红宇的个人博客

2019牛客多校第一场E ABBA（DP）题解

发布日期：2021-08-19 22:02:34 浏览次数：11 分类：技术文章

本文共 1219 字，大约阅读时间需要 4 分钟。

题意：问你长度为2 * （n+m）的字符串由（n+m）个A和B组成，要求有n个AB子序列和m个BA子序列，这样的串有几个

思路：

假设有一个合法串，因为子序列n个AB和m个BA，那么显然有前n个A必为AB的A，前m个B必为BA的B。因为如果我前n个A中有一个是BA的A，那我是不是可以从更后面随便找一个A给这个B用，那么显然前n个A必为AB的A。

我们假设DP[i][j]为i个Aj个B，放A：

如果i < n那么可以直接放这个A，理由如上

如果i >= n，那么我们要确保这个A能给前面的B当BA用，那么当前BA需要的A是min(j, m)个，已经给他了i - n个，故(i - n) < min(j, m)则还可以继续放。

代码：

#include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include 
            
             #include
             
              using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 2e3 + 5;const int M = 50 + 5;const ull seed = 131;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;ll dp[maxn][maxn];int main(){ int n, m; while(~scanf("%d%d", &n, &m)){ for(int i = 0; i <= n + m; i++){ for(int j = 0; j <= n + m; j++){ dp[i][j] = 0; } } dp[0][0] = 1; for(int i = 0; i <= n + m; i++){ for(int j = 0; j <= n + m; j++){ if(i < n || (i - n) < min(m, j)){ //push A dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD; } if(j < m || (j - m) < min(n, i)){ //push B dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % MOD; } } } printf("%lld\n", dp[n + m][n + m]); } return 0;}

转载于:https://www.cnblogs.com/KirinSB/p/11209560.html

转载地址：https://blog.csdn.net/weixin_30955341/article/details/98826149 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：iOS常用代码

下一篇：P1364 医院设置

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章