| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
此题目求含有的最大可匹配字符串数目,然后L-Max就是答案了 f[0] = 0;
FORi(1,L+1,1)
{
f[i] = f[i-1];
FORj(0,W,1)
{
if( len[j]<=i )
{
if( dic[j][len[j]-1]==in[i-1])
{
r1 = i-1;
r2 = len[j]-1;
while(r1>=0 && r2>=0)
{
if( dic[j][r2]==in[r1])
r2--;
r1--;
}
if(r2<0)
{//find it
if(r1<0)
{
//f[i] = TMIN(f[i],i-len[j]);
f[i] = TMAX(f[i],len[j]);
}
else
{
//f[i] = TMIN(f[i],i-1-r1-len[j] + f[r1+1]);
f[i] = TMAX(f[i],len[j]+f[r1+1]);
}
}
}
}
}
}
注释掉的是按照对于每个位置,可删除的最小字符数量,然后答案就是f[L]
非注释掉的是按照对于每个位置,可匹配的最大字符数量,然后总数L-f[L]
这两种方法都可以过,有区别吗?
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator