글 읽기 - N^3 방법으로 풀었는데; 타임리밋이 아니고 롱엔써가 나네요;

na982 8년 전 0

재귀형태로 디피를 구성했는데, 어디가 비는 구간이 있는지 답이 늘리게 나오네요;

고수님이 크리티컬 인풋좀 제공 부탁드려요

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define SIZE	(4002)
char a[SIZE], b[SIZE];
int cache[SIZE][SIZE];

int max_val;
int solve(int a_index, int b_index){
	if(a[a_index] == 0 || b[b_index] == 0)	return 0;

	int& ret = cache[a_index][b_index];
	if(ret != -1)		return ret;

	if(a[a_index] == b[b_index]){
		ret = solve(a_index + 1, b_index + 1) + 1;
		max_val = max(max_val, ret);
	} else{
		ret = 0;
		solve(a_index + 1, b_index);
		solve(a_index, b_index + 1);
	}
	return ret;
}

int main()
{
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(cache, -1, sizeof(cache));

	scanf("%s %s", &a[1], &b[1]);
	max_val = 0;
	solve(1, 1);
	printf("%d\n", max_val);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

N^3 방법으로 풀었는데; 타임리밋이 아니고 롱엔써가 나네요;

na982 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말