pku 3726 Windy's ABC
题意:
给一个由ABC三种字母构成的长度不超过500的字串.
定义这个串的合法副本为:
原串任意位置字母的下标,与它在新串中的下标绝对值之差不超过 Ri.
求合法副本的种类数.
注:
1. 原串本身也是个合法副本
2. 求的是不同串的种类数, "A1B2B3A4" 和 "A1B3B2A4" 算同一种.
解:
先通过O(n)的递推, 求出每种字母在前k位中至少需要/至多能出现多少次, 然后500^3的DP.
对一个合法的状态(i,j,k)(分别表示3种字母的个数), 扩展它的3种后续状态.
这里不用检查扩展出的新状态的合法性, 因为到下一步DP时, 只有合法的状态才会被继续扩展. 这是这题解法处理的巧妙之处.
代码:
1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6 const int MOD = 20090305;
7 char ch[3] = {'A','B','C'};
8 int n[3][510][2];
9 int dp[2][510][510];
10 int R[3],L;
11 char S[510];
12 int T;
13
14 void prepare(){
15 int i,j,k;
16 int c[510];
17 memset(n,0,sizeof(n));
18 for(i=0; i<3; i++){
19 int cnt = 0;
20 for(j=0; j<L; j++){
21 if(S[j]-'A' == i) cnt++;
22 //printf("%d,%d,%d ",i,j,cnt);
23 if(j>=R[i]) n[i][j-R[i]][1] = cnt;
24 if(j<L-R[i]) n[i][j+R[i]][0] = cnt;
25 }
26 for(j=0; j<R[i]; j++){
27 n[i][L-1-j][1] = cnt;
28 n[i][j][0] = 0;
29 }
30 }
31 }
32
33 int dodp(){
34 int l,i,j,k;
35 int ans = 0;
36 memset(dp,0,sizeof(dp));
37 for(i=0; i<L; i++)
38 for(j=0; j<L; j++)
39 dp[0][i][j] = 1;
40 for(l=0; l<L; l++){
41 int p1=l%2, p2=(l+1)%2;
42 memset(dp[p2],0,sizeof(dp[p2]));
43 for(i=n[0][l][0]; i<=n[0][l][1]; i++){
44 for(j=n[1][l][0]; j<=n[1][l][1]; j++){
45 k = l+1-i-j;
46 //printf("s%d,%d,%d ",l,i,j);
47 if(k<n[2][l][0] || k>n[2][l][1]) continue;
48 if(!dp[p1][i][j]) continue;
49 //printf("y%d,%d,%d(%d) ",l,i,j,dp[p1][i][j]);
50 if(l==L-1){ ans += dp[p1][i][j]; continue; }
51 dp[p2][i+1][j] = (dp[p2][i+1][j]+dp[p1][i][j]) % MOD;
52 dp[p2][i][j+1] = (dp[p2][i][j+1]+dp[p1][i][j]) % MOD;
53 dp[p2][i][j] = (dp[p2][i][j]+dp[p1][i][j]) % MOD;
54 }
55 }
56 }
57 return ans;
58 }
59
60 int main(){
61 int i,j,k;
62 scanf("%d",&T);
63 while(T--){
64 scanf("%d %d %d",R,R+1,R+2);
65 scanf("%s",S);
66 L = strlen(S);
67 prepare();
68 printf("%d\n",dodp());
69 }
70 return 0;
71 }
72
posted on 2009-06-29 21:44
wolf5x 阅读(286)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc