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

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

Posted by Baileys at 2015-02-23 21:05:55 on Problem 2192 and last updated at 2015-02-23 21:06:28
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[205], b[205], c[410];
int la, lb, lc, ans[205][205], res[410], 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