每日一题 5.29 管道取珠

首先转化问题 可以换一种理解方式
两个人在两个独立的装置里取球 输出队列相同的方案数
因为对于每一种输出队列 第一个人有ai种方案 第二个人有ai种方案
那么两个人输出队列相同的方案总数就是ai*ai
然后就是一个很简单的dp题目了 dp[i][j][k][l]表示第一个人在上管道取了i个 下取了j个 第二个人在上取了k个 下取了l个 l=i+j-k
两个人的输出队列相同的方案数 然后已知答案就是 dp[z][m][n]
然后思考如何转状态转移 根据dp状态的定义 当目前两个人取的球的个数相同才可能发生转移 然后讨论两个人当前从那根管道取的球
空间上有那么一点问题 但是看到第一维可以滚动掉 放心了
代码有详细注释

#include <bits/stdc++.h>
using namespace std;
const int N=505;
const int mod=1024523;
int n,m,dp[2][N][N];
string a,b;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    cin>>a>>b;a=' '+a,b=' '+b;
    dp[0][0][0]=1;
    int z=0;
    for(int i=0;i<=n;i++,z^=1)///第一个人 取上 i个
        for(int j=0;j<=m;j++)/// 1 取下 j个
            for(int k=0;k<=n;k++){/// 2 取上 k 个
                int l=i+j-k;
                int &x=dp[z][j][k];///基础态
                if(l<0||l>m)continue;
                if(a[i+1]==a[k+1])dp[z^1][j][k+1]=(dp[z^1][j][k+1]+x)%mod;
                if(a[i+1]==b[l+1])dp[z^1][j][k]=(dp[z^1][j][k]+x)%mod;
                if(b[j+1]==a[k+1])dp[z][j+1][k+1]=(dp[z][j+1][k+1]+x)%mod;
                if(b[j+1]==b[l+1])dp[z][j+1][k]=(dp[z][j+1][k]+x)%mod;
                x=0;///更新清零
            }
    cout<<dp[z][m][n]<<endl;
    return 0;
}