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

WA到吐了……各位看看怎么回事吧,用的复杂度O(nm)的算法

Posted by jeremy1022 at 2013-09-14 10:32:24 on Problem 2127
#include <stdio.h>
#include <string.h>
#define MAX_LEN 500
int f[MAX_LEN + 10][MAX_LEN + 10];
int path[MAX_LEN + 10];
int a[MAX_LEN + 10], b[MAX_LEN + 10];
int output[MAX_LEN + 10];
int m1, m2;

int main(){
	int i, j, max, last, start;
	scanf("%d", &m1);
	for(i = 1; i <= m1; i++)
		scanf("%d", &a[i]);
	scanf("%d", &m2);
	for(j = 1; j <= m2; j++)
		scanf("%d", &b[j]);
	memset(f, 0, sizeof(f));
	memset(path, -1, sizeof(path));
	for(i = 1; i <= m1; i++){
		max = 0;
		last = -1;
		for(j = 1; j <= m2; j++){
			f[i][j] = f[i - 1][j];
			if(a[i] > b[j] && f[i- 1][j] > max){
				max = f[i - 1][j];
				last = j;
			}
			if(a[i] == b[j]){
				f[i][j] = max + 1;
				path[j] = last;
			}
		}
	}
	max = 0;
	start = 0;
	for(j = 1; j <= m1; j++){
		if(f[m1][j] > max){
			max = f[m1][j];
			start = j;
		}
	}
	printf("%d\n", max);
	int count = 0;
	if(start > 0){
		do{
			output[max - count - 1] = b[start];
			count++;
			start = path[start];
		}while(start != -1);
	}
	for(i = 0; i < max - 1; i++)
		printf("%d ", output[i]);
	if(i > 0)
		printf("%d\n", output[i]);
	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