Posted on 2011-11-29 14:16
C小加 閱讀(1433)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
解題報(bào)告
原題地址：
http://acm.nyist.net/JudgeOnline/problem.php?pid=336簡(jiǎn)單DP。月賽的時(shí)候沒(méi)去開(kāi)這道題，本想把簡(jiǎn)單題先搞定的，不過(guò)悲劇了。
我剛開(kāi)始很快想出了一種結(jié)構(gòu)，但超內(nèi)存了，然后試著加上滾動(dòng)數(shù)組，發(fā)現(xiàn)不能用，只能換思路。
后來(lái)想的思路有點(diǎn)復(fù)雜，有好多情況沒(méi)有考慮到，繞了好多彎路才AC。
狀態(tài)轉(zhuǎn)移方程式：
f[j+1]=(f[j]+f[j+1])%10003;j+1為B串中第j個(gè)點(diǎn)。
第j個(gè)點(diǎn)的組數(shù)=前一個(gè)元素中第j個(gè)點(diǎn)的組數(shù)+前一個(gè)元素中的第j-1個(gè)點(diǎn)的元素的組數(shù)。
在遍歷A串的過(guò)程中更新f[j+1]。
注意f[0]初始化為1，其他為0。
后來(lái)我用map 優(yōu)化了一下，速度反而降低了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=100003;
char A[MAXN];
char B[1003];
int f[1003];
int main()
{
//freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
//memset(f,0,sizeof(f));
scanf("%s %s",A,B);
int numa=strlen(A);
int numb=strlen(B);
if(numa<numb)
{
printf("0\n");
continue;
}
else if(numa==numb)
{
if(!strcmp(A,B))
{
printf("1\n");
continue;
}
else printf("0\n");
}
else
{
memset(f,0,sizeof(f));
f[0]=1;
for(int i=0;i<numa;i++)
{
for(int j=numb-1;j>=0;j--)
{
if(j>i) continue;
//if(numa-i<=numb-j) continue;
if(A[i]==B[j])
{
f[j+1]=(f[j]+f[j+1])%10003;
}
}
}
printf("%d\n",f[numb]);
}
}
return 0;
}