글 읽기 - 11066파일합치기 DP 질문

sk7755 6년 전 0

다른분들 소스 보니까 dp배열 말고 path index를 저장하는 이차원배열을 하나 더 사용하셨더라구요.

그 배열을 이용해서 풀면 시간이 현격하게 줄던데

원리가 궁금합니다.

#include <cstdio>

inline int min(int a, int b)
{
	return a > b ? b : a;
}

int main()
{
	int dp[501][501] = { 0, };
	int w[501] = { 0, };

	int t;
	scanf("%d", &t);

	while (t--)
	{
		int k;

		scanf("%d", &k);

		for (int i = 1; i <= k; i++)
			scanf("%d", &w[i]);

		for (int i = 1; i <= k; i++)
			w[i] += w[i - 1];

		for (int i = 1; i < k; i++)
		{
			for (int j = 1; j <= k - i; j++)
			{
				dp[j][i + j] = 1000000000;
				for (int s = j; s < i + j; s++)
					dp[j][i + j] = min(dp[j][i + j], dp[j][s] + dp[s + 1][i+j]);

				dp[j][i + j] += w[i + j] - w[j - 1];
			}
		}

		printf("%d\n", dp[1][k]);
	}

	return 0;
}

kinssang 6년 전 1

knuth's optimization 이라는 방법입니다 자세한건 구글 검색을...

sk7755 6년 전 0

감사합니다.

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

문제

문제

출처

ICPC

11066파일합치기 DP 질문

sk7755 6년 전 0

kinssang 6년 전 1

sk7755 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말