글 읽기 - 행렬곱샘 순서 문제, DP 질문

Coxie 5년 전 0

아무리 봐도 맞는것 같지만, 틀렸습니다가 뜹니다.

소스코드의 문제점이 무엇인지 궁금합니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//모든걸 long long으로 하여 overflow를 방지한다!
ll N, r[555], c[555], D[555][555];
//D[i][j]는 i(포함)부터 j(포함)까지 행렬을 곱했을 때 횟수
int main()
{
	for (ll i = 0; i < 555; ++i)
		for (ll j = 0; j < 555; ++j)
			D[i][j] = INT_MAX * 3LL;//무한대 초기화
	cin >> N;
	for (ll i = 1; i <= N; ++i)
		cin >> r[i] >> c[i], D[i][i] = 0L; //한개 짜리는 0

	for (ll i = 1; i <= N; ++i)//시작부분
		for (ll j = i; j <= N; ++j)//끝부분
			for (ll k = i; k < j; ++k)//중간부분
				D[i][j] = min(D[i][j], D[i][k] + D[k + 1][j] + r[i] * c[k] * c[j]);

	cout << D[1][N];
	return 0;
}

dlwodnsdl 5년 전 1

이렇게 코드를 돌리시면

D[i][j]가 D[k+1][j]보다 먼저 돌려지는 경우가 발생합니다.

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

문제

문제

출처

ICPC

행렬곱샘 순서 문제, DP 질문

Coxie 5년 전 0

dlwodnsdl 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말