首页 > 代码库 > BZOJ1566 【NOI2009】管道取珠
BZOJ1566 【NOI2009】管道取珠
题面
这是一道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 }
BZOJ1566 【NOI2009】管道取珠
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。