題目鏈接
solution
我們可以將問題轉化為進行兩次游戲，最終輸出的序列相同的方案數，
為什么可以這么轉化呢？我們嘗試用式子表示這個新問題，對于一種序列\(i\)，如果在一次游戲中取到他的方案數為\(a_i\)，那么根據乘法原理，在兩次游戲中都取到他的方案數就是\(a_i^2\)，那么所有可能序列的方案數之和自然就是\(\sum a_i^2\)了，
那這個問題怎么做呢？我們設狀態\(f[i][j][k][t]\)表示在第一次游戲中第一個序列還剩下了\(i\)個球，第二個序列還剩下\(j\)個求，在第二次游戲中第一個序列還剩下\(k\)個球，第二個序列還剩下\(t\)個求的方案數，
最后的答案自然就是\(f[n][m][n][m]\)，
然后考慮轉移，對于狀態\(f[i][j][k][t]\)，我沒列舉在每次游戲中最后加入的一個球，然后就可以得到轉移方程如下:
f[i][j][k][t]=f[i-1][j][k-1][t] + f[i-1][j][k][t-1]+f[i][j-1][k - 1][t]+f[i][j-1][k][t-1]
根據狀態的定義我們可以知道肯定滿足\(i+j=k+t\)，所以我們只需要列舉\(i,j,k\)這三維就可以算出第4維，不需要列舉第四維，時空復雜度為\(O(n^3)\)，
時間沒問題，但空間會爆炸，所以將第一維滾動一下即可，
code
/*
* @Author: wxyww
* @Date: 2020-05-28 14:57:30
* @Last Modified time: 2020-05-28 16:07:27
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 510,mod = 1024523;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1; c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0'; c = getchar();
}
return x * f;
}
int f[2][N][N];
char s[N],t[N];
int main() {
int n = read(),m = read();
scanf("%s",s + 1);
scanf("%s",t + 1);
f[0][0][0] = 1;
for(int i = 0;i <= n;++i) {
int tmp = i & 1;
for(int j = 0;j <= m;++j) {
for(int k = 0;k <= min(n,i + j);++k) {
if(!i && !j && !k) {f[tmp][j][k] = 1;continue;}
f[tmp][j][k] = 0;
int tt = i + j - k;
if(i && k && s[i] == s[k]) {
f[tmp][j][k] += f[tmp ^ 1][j][k - 1];
f[tmp][j][k] >= mod ? f[tmp][j][k] -= mod : 0;
}
if(i && tt && s[i] == t[tt]) {
f[tmp][j][k] += f[tmp ^ 1][j][k];
f[tmp][j][k] >= mod ? f[tmp][j][k] -= mod : 0;
}
if(j && k && t[j] == s[k]) {
f[tmp][j][k] += f[tmp][j - 1][k - 1];
f[tmp][j][k] >= mod ? f[tmp][j][k] -= mod : 0;
}
if(j && tt && t[j] == t[tt]) {
f[tmp][j][k] += f[tmp][j - 1][k];
f[tmp][j][k] >= mod ? f[tmp][j][k] -= mod : 0;
}
}
}
}
cout<<f[n & 1][m][n]<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/20761.html
標籤：C++
上一篇：STM32F103驅動M24256 256k存盤芯片進行讀寫
下一篇：C++ 名稱空間嵌套