首页 > 代码库 > BZOJ1566 【NOI2009】管道取珠

BZOJ1566 【NOI2009】管道取珠

题面

 

这是一道DP神题,直到我写下这句题解时也没有想明白……

首先,这道题要我们求所有(不同输出序列的方案数)的平方和,于是我们当然就想到求所有不同输出序列的方案数……(大雾) 。这道题一个巧妙的地方就在于对问题的转化。(以下摘自BYVoid大神的题解)

假设同时有两个人X & Y在玩这个游戏,Xup取了i个珠子(不一定连续),从down取了j个珠子,取出来的珠子组成的序列为Q操作序列为x,Yup取了k个珠子,从down取了l个珠子,取出来的珠子组成的序列也为Q,操作序列为y,那么我们就得到了一个有序对(xy,f[i][j][k][l]即表示有序对(xy)的数量。两个有序对不相同当且仅当xy不同时相同

下面证明f[i][j][k][l]即为所求。

已知:取出珠子的序列为Qxy分别为一种取珠方法(可相同), 取出Q的方案数为a

求证:有序对(xy)的数量等于a2

因为取出Q的方案数为a,所以x & y都有a种取值,且x & y彼此独立,故对于x的每一个取值,y都有a种取值,故有序对(xy)的数量为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 }

 

BZOJ1566 【NOI2009】管道取珠