Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

此题目求含有的最大可匹配字符串数目,然后L-Max就是答案了

Posted by saintqdd at 2011-03-10 14:41:32 on Problem 3267 and last updated at 2011-03-10 14:42:53
		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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator