Posted on 2011-11-29 14:16
C小加 阅读(1418)
评论(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;
}