Posted on 2011-11-29 14:16
C小加 閱讀(1429)
評論(1) 編輯 收藏 引用 所屬分類:
解題報告
原題地址：
http://acm.nyist.net/JudgeOnline/problem.php?pid=336簡單DP。月賽的時候沒去開這道題，本想把簡單題先搞定的，不過悲劇了。
我剛開始很快想出了一種結構，但超內存了，然后試著加上滾動數組，發現不能用，只能換思路。
后來想的思路有點復雜，有好多情況沒有考慮到，繞了好多彎路才AC。
狀態轉移方程式：
f[j+1]=(f[j]+f[j+1])%10003;j+1為B串中第j個點。
第j個點的組數=前一個元素中第j個點的組數+前一個元素中的第j-1個點的元素的組數。
在遍歷A串的過程中更新f[j+1]。
注意f[0]初始化為1，其他為0。
后來我用map 優化了一下，速度反而降低了。
#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;
}