글 읽기 - 2073 수도배관공사 길이를 만들 수 없을때 조건이 있나요..?

hakgb11 8년 전 1

안될때의 조건이 필요할꺼 같은데 -_ㅠ 푸신분들 자비를 부탁드립니다.

혹시 2차원 DP를 사용해서 냅색문제 처럼 접근했는데.. 맞는 풀이인지 궁금합니다 ㅠ

#include <iostream>
#include <utility>
#include <limits.h>
#include <fstream>
#include <string>
#include <string.h>
#include <queue>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>

typedef long long ll;
using namespace std;



int main(){
#ifdef _CONSOLE
	freopen("input.txt", "r", stdin);
#endif
	int n, m;
	cin >> n >> m;
	vector<vector<ll> > DP(m + 1, vector<ll>(100001, LLONG_MIN));
	vector<pair<ll, ll> > pipe;
	for (int i = 0; i < m; i++){
		ll  a, b;
		cin >> a >> b;
		pipe.push_back(make_pair(a, b));
	}
	sort(pipe.begin(), pipe.end());
	DP[0][0] = LLONG_MAX;
	for (int i = 0; i <= m; i++)
		DP[i][0] = LLONG_MAX;
	for (int i = 1; i <= m; i++){
		ll cur = pipe[i - 1].first;
		ll flow = pipe[i - 1].second;
		for (int j = 0; j < cur; j++)
			DP[i][j] = DP[i - 1][j];
		for (int j = cur; j <= 100001; j++){
			if (DP[i - 1][j - cur] == LLONG_MIN)
				continue;
			else{
				ll a = DP[i - 1][j];
				DP[i][j] = max(a, min(DP[i - 1][j - cur], flow));
			}
		}
	}
	if (DP[m][n] < 0)
		cout << "0" << endl;
	else
		cout << DP[m][n] << endl;
}

kesakiyo 8년 전 2

안될만한 이유가 있으니까 안되는 걸꺼에요 :-)

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

문제

문제

출처

ICPC

2073 수도배관공사 길이를 만들 수 없을때 조건이 있나요..?

hakgb11 8년 전 1

kesakiyo 8년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말