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

Re:HDU上1501已经AC了呀,怎么贴过来还是WA,O(N)的复杂度

Posted by 14311210809 at 2015-07-16 20:41:17 on Problem 2192
In Reply To:HDU上1501已经AC了呀,怎么贴过来还是WA,O(N)的复杂度 Posted by:Baileys at 2015-02-23 21:05:55
> ans[i][j]用来记录长为i的字串1和长为j的字串2是否可以合成字串3
> 如果可以合成就标记res[i+j]=1
> 当然了,使得一个res[i+j]=1的情况可以有很多种,所以就开一个表,最大200*200
> 每次都斜着一行一行扫,极限情况也判得很快~
> 
> 
> #include <stdio.h>
> #include <string.h>
> char a[400], b[400], c[800];
> int la, lb, lc, ans[400][400], res[800], i, j, k;
> int main()
> {
> 	int t, v;
> 	scanf("%d", &t);
> 	for(int p = 1;p <= t;p++)
> 	{
> 		scanf("%s%s%s", a+1, b+1, c+1);
> 		la = strlen(a+1), lb = strlen(b+1), lc = strlen(c+1);
> 		memset(ans, 0, sizeof(ans));
> 		memset(res, 0, sizeof(res));
> 		ans[0][0] = res[0] = 1;
> 		for(k = 1;k <= la+lb;k++)
> 		{
> 			if(!res[k-1])
> 			{
> 				printf("Data set %d: no\n", p);
> 				break;
> 			}
> 			for(j = 0;j <= k;j++)
> 			{
> 				i = k-j;
> 				if(j > lb || i > la)
> 					continue;
> 				if(!j && ans[0][k-1] && a[k]==c[k])
> 					ans[0][k] = res[k] = 1;
> 				else if(!i && ans[k-1][0] && b[k]==c[k])
> 					ans[k][0] = res[k] = 1;
> 				else if((ans[j][i-1])&&a[i]==c[k]||(ans[j-1][i]&&b[j]==c[k]))
> 					ans[j][i] = res[k] = 1;
> 			}
> 		}
> 		if(res[la+lb])
> 			printf("Data set %d: yes\n", p);
> 		//for(int j = 0;j <= lb;j++)for(int i = 0;i <= la;i++)printf("%d%c", ans[j][i], " \n"[i==la]);
> 	}
> 	return 0;
> }

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