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 閱讀(299)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc