글 읽기 - DP를 이용해서 풀었는데...반례를 못찾겠습니다

qkr9990 6년 전 0

5 6
011100
001000
010100
001010
000100

일때,

먼저 DP테이블을 이용해서 문제를 푸는데

DP테이블에 1이상인것은 그 다이아몬드모양에다가,

다이아몬드의 아래꼭지(아래꼭지부터 왼쪽꼭지까지)와 오른꼭지(오른쪽꼭지부터 아래꼭지까지)가 1일때

대각선 오른쪽 위의 DP값을 더하도록하고 이를이용하여 최대값을 구하였습니다.

하지만 답이 틀리다고 나오네 ㅠ

반례부탁드립니다.

#include <cstdio>

int result = 0;
char mat[751][752];
int DP[751][751];
int R,C;

int main() {
	scanf("%d %d",&R,&C);
	for(int i=0;i<R;i++)
		scanf("%s",mat[i]);

	for(int i=0;i<R;i++) {
		for(int j=0;j<C;j++) {
			if(mat[i][j] == '1'){
				DP[i][j] = mat[i][j]-'0';
				if(i-1>=0 && j+1<C) {
					bool add = true, tmp_a = false, tmp_b = false;
					for(int z=0;z<DP[i-1][j+1];z++) {
						tmp_a = mat[i+z][j+(DP[i-1][j+1]*2)-z] == '1';
						tmp_b = mat[i+DP[i-1][j+1]-z][j+DP[i-1][j+1]-z] == '1';
						add = add && tmp_a && tmp_b;
					}
					if(add && tmp_a && tmp_b)
						DP[i][j] = DP[i-1][j+1]+1;
				}
				result = DP[i][j]>result?DP[i][j]:result;
			}
		}
	}
	printf("%d\n",result);
	return 0;
}

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

문제

문제

출처

ICPC

DP를 이용해서 풀었는데...반례를 못찾겠습니다

qkr9990 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말