为毛输出不对?

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001,MAXL=22,MAXM=5002,IMP=0x7FFFFFF;
using namespace std;
struct TTrie
{
struct Trie_node
{
Trie_node *c[26];
int Wm;
Trie_node():Wm(0){memset(c,0,sizeof(c));}
};
Trie_node *root;
void ins(Trie_node *&p,int *S,int L,int Wm)
{
if (!p) p=new Trie_node();
if (L==0) p->Wm|=Wm;
else ins(p->c[*S],S+1,L-1,Wm);
}
int find(Trie_node *p,int *S,int L)
{
if (!p) return 0;
if (L==0) return p->Wm;
else return find(p->c[*S],S+1,L-1);
}
}Trie;
int N,M,MaxL,Ans1,Ans2;
char Word[MAXL],Passage[MAXM];
int W[MAXL],P[MAXM],F[MAXM][4][2],Mat[MAXM][MAXL];
void init()
{
int i,j,len,type;
freopen("lostcity.in","r",stdin);
freopen("lostcity.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
{
scanf("%s",Word);
len=strlen(Word)-2;
if (len>MaxL) MaxL=len;
for (j=1;j<=len;j++)
W[j]=Word[j+1]-'a';
if (Word[0]=='n')
type=1;
else if (Word[0]=='v')
type=2;
else
type=4;
Trie.ins(Trie.root,W+1,len,type);
}
scanf("%s",Passage);
M=strlen(Passage)-1;
for (j=1;j<=M;j++)
P[j]=Passage[j-1]-'a';
for (i=1;i<=M;i++)
for (j=1;j<=MaxL;j++)
Mat[i][j]=-1;
}
inline int Min(int a,int b){return a<b?a:b;}
int dynamic()
{
int i,j,k,p;
for (p=0;p<=1;p++)
for (i=0;i<4;i++)
for (j=0;j<=M;j++)
F[j][i][p]=IMP;
F[0][0][0]=0;
for (k=p=1;k<=M;k++,p=!p)
{
for (i=1;i<=M;i++)
{
F[i][0][p]=F[i][1][p]=F[i][2][p]=F[i][3][p]=IMP;
for (j=i-1;j>=i-MaxL && j>=0;j--)
{
if (Mat[i][i-j]==-1)
Mat[i][i-j]=Trie.find(Trie.root,P+j+1,i-j);
int Wm=Mat[i][i-j];
if (Wm&1)
{
F[i][0][p]=Min(F[i][0][p],F[j][1][p]+1);
F[i][0][p]=Min(F[i][0][p],F[j][3][p]+1);
F[i][0][p]=Min(F[i][0][p],F[j][0][!p]+1);
F[i][0][p]=Min(F[i][0][p],F[j][1][!p]+1);
}
if (Wm&2)
{
F[i][1][p]=Min(F[i][1][p],F[j][0][p]+1);
F[i][1][p]=Min(F[i][1][p],F[j][2][p]+1);
}
if (Wm&4)
{
F[i][2][p]=Min(F[i][2][p],F[j][0][p]+1);
F[i][2][p]=Min(F[i][2][p],F[j][2][p]+1);

F[i][3][p]=Min(F[i][3][p],F[j][1][p]+1);
F[i][3][p]=Min(F[i][3][p],F[j][3][p]+1);
F[i][3][p]=Min(F[i][3][p],F[j][0][!p]+1);
F[i][3][p]=Min(F[i][3][p],F[j][1][!p]+1);
}
}
}
Ans2=Min(F[M][0][p],F[M][1][p]);
if (Ans2<IMP)
return k;
}
}
int main()
{
init();
Ans1=dynamic();
printf("%dn%dn",Ans1,Ans2);
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1299
难度
5
分类
字符串 | 动态规划 点击显示
标签
递交数
114
已通过
36
通过率
32%
被复制
3
上传者