글 읽기 - dp와 부분합을 이용해 풀었는데 TLE가 나옵니다.

zxcv551133 5년 전 1

어떤 부분에서 개선할 수 있을 지 도움 부탁드립니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
const int INF = -99999999;
vector<vector<int>> memo;
vector<int> pSum;

vector<int> preSum(const vector<int>& v) {
	vector<int> pSum(v.size() + 1);
	for (int i = 0; i < v.size(); i++) {
		pSum[i + 1] = pSum[i] + v[i];
	}
	return pSum;
}

int rangeSum(int a, int b) {
	return pSum[b + 1] - pSum[a];
}

//start 부터 x개의 구간을 나누었을 때의 최대합 
int go(int start, int x) {
	if (x == 0) {
		return 0;
	}
	if (start >= n) {
		return INF*10;
	}
	int ret = memo[start][x];	
	if (ret != INF) return ret;
	ret = go(start + 1, x);
	for (int i = 0; i < n; i++) {
		ret = max(ret, rangeSum(start, i) + go(i + 2, x - 1));
	}
	return ret;	
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	cin >> n >> m;
	vector<int> ar(n);
	memo.assign(n, vector<int>(n, INF));
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
	}
	pSum = preSum(ar);
	int ans = INF;
	
	cout << go(0,m) << '\n';

	return 0;
}

yukariko 5년 전 1

int ret = memo[start][x]; 가 int& ret = memo[start][x];

로 바껴야 할것 같습니다

zxcv551133 5년 전 0

감사합니다

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

문제

문제

출처

ICPC

dp와 부분합을 이용해 풀었는데 TLE가 나옵니다.

zxcv551133 5년 전 1

yukariko 5년 전 1

zxcv551133 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말