글 읽기 - 이 문제 힌트좀 주세요 .. ㅠㅠㅠㅠ

dlgldgld 6년 전 0

문제를 읽어보고 아래 소스처럼 dp로 만들면 최적의해가 나올것 같은데

아무래도 제가 접근방법이 완전히 잘못 된거 같습니다..

힌트 좀 알려주시면 감사하겠습니다!

#include<cstdio>
#include<algorithm>
#define MOD 1000000007
#define INF 2000000000000000001

using namespace std;
unsigned long long dp[61][61], In[61], c[61][61];
int main() {

	int T;
	scanf("%d", &T);
	while (T-- != 0) {
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) { scanf("%lld", &In[i]); }
		sort(In + 1, In + n + 1);
		for (int i = 1; i <= n; i++) {
			dp[i][i] = 1;
			for (int j = i; j <= n; j++) {
				if (c[i][j - 1] == 0) c[i][j - 1] = 1;
				c[i][j] = (c[i][j - 1] * In[j]);
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n - i; j++) {
				int a = j, b = j + i;
				dp[a][b] = INF;
				if (i == 1) dp[a][b] = c[a][b];
				else {
					for (int k = a; k < b; k++) {
						dp[a][b] = min(dp[a][b], ((dp[a][k] * dp[k + 1][b]) * c[a][b]) );
					}
				}
			}
		}
		printf("%lld\n", dp[1][n]%MOD);
	}
}

chogahui05 6년 전 0

힌트 1

TC가 여러개이고, n의 총 합이 100만이라는 거

=> 최소한 O(nlogn)에 해결할 수 있다는 점.

힌트 2

Greedy

일단 정렬까진 맞았습니다.

dlgldgld 6년 전 0

음.. 여전히 더모르겠군요 ㅋㅋㅋㅋㅋ

좀 더 생각해보겠습니다. 답변 감사합니다!!

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

문제

문제

출처

ICPC

이 문제 힌트좀 주세요 .. ㅠㅠㅠㅠ

dlgldgld 6년 전 0

chogahui05 6년 전 0

dlgldgld 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말