【BZOJ】1566: [NOI2009]管道取珠

题解

假如我们非常熟练的看出来，平方和转有序对统计的套路的话，应该就不难了

我们只需要统计(wayA,wayB)生成的序列一样的有序对个数就行

可以用一个\(n^3\)的dp解决

\(dp[i][j][k]\)表示选到第i个，第一个序列用j个上管道的球，第二个序列用了k的上管道的球，要求下一次操作两个球长得一样就可以了

代码

#include <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <map>

//#define ivorysi

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define mo 974711

#define RG register

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 1024523;

int dp[2][505][505],N,M;

char up[505],down[505];

void update(int &x,int y) {

    x = x + y;

    if(x >= MOD) x -= MOD;

}

void Solve() {

    scanf("%d%d",&N,&M);

    scanf("%s",up + 1);scanf("%s",down + 1);

    up[N + 1] = 'C';down[M + 1] = 'D';

    int cur = 0;

    dp[0][0][0] = 1;

    for(int i = 0 ; i < N + M ; ++i) {

	int t = min(i,N);

	memset(dp[cur ^ 1],0,sizeof(dp[cur ^ 1]));

	for(int j = 0 ; j <= t ; ++j) {

	    for(int k = 0 ; k <= t ; ++k) {

		if(up[j + 1] == up[k + 1] && j != N && k != N) update(dp[cur ^ 1][j + 1][k + 1],dp[cur][j][k]);

		if(up[j + 1] == down[i - k + 1]) update(dp[cur ^ 1][j + 1][k],dp[cur][j][k]);

		if(down[i - j + 1] == up[k + 1]) update(dp[cur ^ 1][j][k + 1],dp[cur][j][k]);

		if(down[i - j + 1] == down[i - k + 1]) update(dp[cur ^ 1][j][k],dp[cur][j][k]);

	    }

	}

	cur ^= 1;

    }

    out(dp[cur][N][N]);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

巴特西

【BZOJ】1566: [NOI2009]管道取珠

题解

代码

最新文章

热门文章