#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<set>
using namespace std;
const int INF=0x7fffffff;
const double eps=(1.0e-9);
const double PI=atan2(0.0,-1.0);
int len[4],a[3],dp[2][501][501];
int abss(int x)
{
    return x>0?x:-x;
}
int ok(vector<int>map[],int v,int flag,int now)
{
    if(a[flag]>=abss(v-map[flag][now]))
    return 1;
    return 0;
}
int main()
{
    int cas;
    cin>>cas;
    while(cas--)
    {
        cin>>a[0]>>a[1]>>a[2];
        vector<int>map[3];
        string ss;
        cin>>ss;
        int n=ss.size();
        for(int i=0;i<n;i++)
        map[ss[i]-'A'].push_back(i);
        len[1]=map[0].size();
        len[2]=map[1].size();
        len[3]=map[2].size();
        int s=0,p=1;
        for(int i=0;i<=len[1];i++)
        for(int j=0;j<=len[2];j++)
        dp[0][i][j]=0;
        for(int q=0;q<n;q++)
        {
            for(int i=0;i<=len[1];i++)
            for(int j=0;j<=len[2];j++)
            {
                int now=i+j;
                if(now>n)
                break;
                if(i+1<=len[1]&&ok(map,q,0,i))
                {
                    dp[p][i+1][j]+=dp[s][i][j];
                    dp[p][i+1][j]%=20090305;
                    if(q==0)
                    dp[p][i+1][j]=1;
                }
                if(j+1<=len[2]&&ok(map,q,1,j))
                {
                    dp[p][i][j+1]+=dp[s][i][j];
                    dp[p][i][j+1]%=20090305;
                    if(q==0)
                    dp[p][i][j+1]=1;
                }
                int k=q-i-j;
                if(k>=0&&k+1<=len[3]&&ok(map,q,2,k))
                {
                    dp[p][i][j]+=dp[s][i][j];
                    dp[p][i][j]%=20090305;
                    if(q==0)
                    dp[p][i][j]=1;
                }
                dp[s][i][j]=0;
            }
            s=1-s;
            p=1-p;
        }
        int ans=0;
        for(int i=0;i<=len[1];i++)
        for(int j=0;j<=len[2];j++)
        {
            ans+=dp[s][i][j];
            ans%=20090305;
        }
        cout<<ans<<endl;
    }
    return 0;
}

• Re:谁能看看我的为什么tle呢？！谢谢 (20) liuke 2009-04-06 23:46:35
  • Re:谁能看看我的为什么tle呢？！谢谢 (50) liuke 2009-04-07 00:01:40
• Re:谁能看看我的为什么tle呢？！谢谢 (64) DreamOfGame 2009-04-07 08:12:19