글 읽기 - 무글맵스 질문입니다.

alohajihwan 7년 전 0

알고리즘을 간결하게 짰는데 시간초과가 어떤 부분에서 나는 지 궁금합니다..ㅠㅠ

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<functional>
#include<set>
using namespace std;
#define INF 999999999
#define ll long long	

double Abs(double a)
{
	if (a < 0) return -a;
	else return a;
}
double H, C;
double arr[211];
double dp[211][211][211];
//[p,q]범위에서 p,q가 저장된 위치일때 최소값 반환
double solve(int p, int q, int cnt)
{
	double r = 0;
	if (cnt == 0) {
		
		for (int i = p + 1; i < q; i++) {
			r += Abs(arr[i] - (double)(arr[p] + (arr[q] - arr[p])*(double)(i - p) / (double)(q - p)));
		}
		return r;
	}
	double & ret = dp[p][q][cnt];
	if (ret < INF) return ret;
	
	for (int i = p + 1; i < q; i++) {
		r = 0;
		for (int j = p + 1; j < i; j++) {
			r += Abs(arr[j] - (double)(arr[p] + (arr[i] - arr[p])*(double)(j - p) / (double)(i - p)));
		}
		ret = min(ret, solve(i, q, cnt - 1) + r);
	}
	return ret;
}

int main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> H >> C;
		for (int i = 1; i <= H; i++) scanf("%lf", &arr[i]);
		for (int i = 0; i <= H; i++) for (int j = 0; j <= H; j++) for (int k = 0; k <= C; k++) dp[i][j][k] = INF;

		printf("%.4lf\n",solve(1, H, C - 2) / H);
	}
}

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

문제

문제

출처

ICPC

무글맵스 질문입니다.

alohajihwan 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말