글 읽기 - c++ DP 시간초과인데 수정할 부분을 잘 모르겠네요...

kjw2448 3년 전 0

C++ DP를 이용해서 풀었는데

시간초과가 나서 수정할 부분을 잘 모르겠습니다..ㅠㅠ

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

int n;
vector<pair<int, int>> v;
int DP[1500001];



int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}
	
	for (int i = 1; i < n + 1; i++) {
		DP[i] = DP[i - 1];
		for (int j = 0; j < i; j++) {
			if (j + v[j].first <= i) {
				if (DP[j] + v[j].second >= DP[i]) DP[i] = max(DP[i], DP[j] + v[j].second);
			}
		}
	}

	cout << DP[n];
	
}

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

문제

문제

출처

ICPC

c++ DP 시간초과인데 수정할 부분을 잘 모르겠네요...

kjw2448 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말