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

一次AC,纪念一下^-^

Posted by zhangyufei at 2015-12-13 23:15:21 on Problem 1936
/****************************************************/
/* File        : POJ136.c                          */
/* Author      : Zhang Yufei                        */
/* Date        : 2015-12-13                         */
/* Description : POJ ACM program. (submit:g++)      */
/****************************************************/

#include<stdio.h>
#include<string.h>

// The s and t string in the problem.
char s[100003];
char t[100003];

// The matrix used to calculate MSL.
// The row is too large, so use only 2 lines repeatly.
short matrix[2][100003];

/*
 * Used to deal with one input case.
 */
void butler(void);

/*
 * Initial the matrix before deal with one case.
 */
void init(void);

/*
 * The main program.
 */
int main(void) {
	while(scanf("%s %s", s, t) != EOF) {
		init();
		butler();
	}
	return 0;
}

/*
 * Used to deal with one input case.
 */
void butler(void) {
	int sl = strlen(s);
	int tl = strlen(t);

	for(int i = 1; i <= sl; i++) {
		int r = i % 2;
		for(int j = 1; j <= tl; j++) {
			if(s[i - 1] == t[j - 1]) {
				matrix[r][j] = matrix[1 - r][j - 1] + 1;
			} else {
				if(matrix[1 - r][j] > matrix[r][j - 1]) {
					matrix[r][j] = matrix[1 - r][j];
				} else {
					matrix[r][j] = matrix[r][j - 1];
				}
			}
		}
	}
	
	if(matrix[sl % 2][tl] == sl) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}
}

/*
 * Initial the matrix before deal with one case.
 */
void init(void) {
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < 100003; j++) {
			matrix[i][j] = 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