bzoj1556 (DP)

bzoj 1556 点这里打开题目

题目是求 a^2 求和；

原问题可以转化为：两个人在玩这个东西，问这两个人弄出来的序列相同的有多少种情况，操作方式不同即为一种不同的情况。

就这个问题，参考大佬的DP思想。

DP[t][i][j] 分别表示两人同时第t次取小球，第一人在上面管道取了i个，第二个人在上面管道取了j个所出现相同情况的个数：

我们假设：某一个状态为 DP[t][i][j] 。当第一人取得球和第二个人取得球颜色相同时，那么下一个状态就可以从当前状态转过去；

所以很容易得到状态转移为：每个人都可以取上面和下面的；组合一样四个情况，判断球颜色是否一样：转移。

注意：自己写的时候看清下标。

This is code

#include <iostream>

#include <string.h>

#include <string>

#include <algorithm>

#include <math.h>

#include <queue>

#include <stdlib.h>

#include <stdio.h>

using namespace std;

typedef long long int LL;

const int maxn=;

char a[maxn],b[maxn];

int dp[][maxn][maxn];

const int MOD=;

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    scanf("%s%s",a,b);

    dp[][][]=;

    for(int t=;t<n+m;t++)

    {

        int gd=t%;

        for(int i=;i<=n&&i<=t;i++)

            for(int j=;j<=n&&j<=t;j++)

            {

                if(t-i>m||t-j>m) continue;

                if(a[i]==a[j]) (dp[!gd][i+][j+]+=dp[gd][i][j])%=MOD;

                if(a[i]==b[t-j]) (dp[!gd][i+][j]+=dp[gd][i][j])%=MOD;

                if(b[t-i]==a[j]) (dp[!gd][i][j+]+=dp[gd][i][j])%=MOD;

                if(b[t-i]==b[t-j]) (dp[!gd][i][j]+=dp[gd][i][j])%=MOD;

                dp[gd][i][j]=;

            }

    }

    printf("%d\n",dp[(m+n)%][n][n]);

    return ;

}

巴特西

bzoj1556 (DP)

最新文章

热门文章