这是一道DP神题,直到我写下这句题解时也没有想明白……
首先，这道题要我们求所有（不同输出序列的方案数）的平方和，于是我们当然就想到求所有不同输出序列的方案数……（大雾） 。这道题一个巧妙的地方就在于对问题的转化。（以下摘自BYVoid大神的题解）
假设同时有两个人X & Y在玩这个游戏，设X从up取了i个珠子（不一定连续），从down取了j个珠子，取出来的珠子组成的序列为Q，操作序列为x，Y从up取了k个珠子，从down取了l个珠子，取出来的珠子组成的序列也为Q，操作序列为y，那么我们就得到了一个有序对（x，y），f[i][j][k][l]即表示有序对（x，y）的数量。两个有序对不相同当且仅当x和y不同时相同。
下面证明f[i][j][k][l]即为所求。
已知：取出珠子的序列为Q，x和y分别为一种取珠方法（可相同）， 取出Q的方案数为a；
求证：有序对（x，y）的数量等于a2。
因为取出Q的方案数为a，所以x & y都有a种取值，且x & y彼此独立，故对于x的每一个取值，y都有a种取值，故有序对（x，y）的数量为a2，命题得证。
博主是个超级大傻*，连空间优化到n2都不会，请各路大神指教。
1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <queue> 5 #include <stack> 6 #include <cstdio> 7 #include <string> 8 #include <vector> 9 #include <cstring> 10 #include <complex> 11 #include <cstdlib> 12 #include <iostream> 13 #include <algorithm> 14 #define rg register 15 #define ll long long 16 using namespace std; 17 18 inline int gi() 19 { 20 rg int r = 0; rg bool b = 1; rg char c = getchar(); 21 while (c < ‘0‘ || c > ‘9‘) { if (c == ‘-‘) b = 0; c = getchar(); } 22 while (c >= ‘0‘ && c <= ‘9‘) { r = r * 10 + c - ‘0‘, c = getchar(); } 23 if (b) return r; return -r; 24 } 25 26 const int inf = 2147483647, N = 505, MOD = 1024523; 27 int n,m,f[N][N][N]; 28 char S[N],X[N]; 29 30 inline void input() 31 { 32 freopen ("!.in", "r", stdin); 33 n=gi(), m=gi(); 34 scanf("%s%s",S+1,X+1); 35 } 36 37 inline void output() 38 { 39 freopen ("!.out", "w", stdout); 40 printf("%d\n",f[n][m][n]); 41 } 42 43 inline void cal(int &t,int d) { t+=d; if (t >= MOD) t-=MOD; } 44 45 inline void solve() 46 { 47 int i,j,k,l,tmp; 48 f[0][0][0]=1; 49 for (i=0; i<=n; i++) 50 for (j=0; j<=m; j++) 51 for (k=0; k<=n; k++) 52 { 53 tmp=f[i][j][k], l=i+j-k; 54 if (!tmp || !l || l > m) continue; 55 if (S[i+1] == S[k+1]) 56 cal(f[i+1][j][k+1],tmp); 57 if (X[j+1] == S[k+1]) 58 cal(f[i][j+1][k+1],tmp); 59 if (S[i+1] == X[l+1]) 60 cal(f[i+1][j][k],tmp); 61 if (X[j+1] == X[l+1]) 62 cal(f[i][j+1][k],tmp); 63 } 64 } 65 66 int main() 67 { 68 input(); 69 solve(); 70 output(); 71 return 0; 72 }
原文：http://www.cnblogs.com/y142857/p/7197649.html