앳코더90 - 011 - Gravy Jobs（★6）

https://atcoder.jp/contests/typical90/tasks/typical90_k

011 - Gravy Jobs（★6）

 

N개의 일 

d, c, s 가 주어진다. d일 시작하여 c일동안 진행되며 s원을 준다.

서브 태스크 문제이며 가장 돈을 많이 벌 수있게 일을 선택하는 것이다. 문제를 읽어봤을때 들었던 생각은 TSP문제였고 서브태스크들을 보고 각각

N<=8 브루트포스
N<=20 비트마스크dp

N<=5000 무언가?

라는 생각에 서브태스크 2까지만 뚫어보자는 생각으로 dp를 짜려고 했는데 다시 읽어보니 dp를 안쓰고 비트마스킹만으로도 N<=20 까지는 통과 할 수 있을것 같아서 정렬후 비트마스킹으로 해결했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 200000000;
const double pi = 3.14159265358979;
const ll MOD = 987654321;

void yesno(bool a)
{
	if(a)
		cout << "Yes\n";
	else
		cout << "No\n";
}

struct work
{
	ll d, c, s;
};

int N;
vector<work> v;
ll dp[5009][5009];

ll cache(int cur)
{
	ll curT = 0;;
	ll curC = 0;
	for (int i = 0; i < N; i++)
	{
		if ((cur & (1 << i)) == 0)
			continue;

		if (curT + v[i].c > v[i].d)
			return -1;

		curT += v[i].c;
		curC += v[i].s;
	}

	return curC;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;

	rep(i, N)
	{
		ll a, b, c;
		cin >> a >> b >> c;

		v.push_back({ a,b,c });
	}
	sort(v.begin(), v.end(), [](const work& a, const work& b) {
		if (a.d != b.d) return a.d < b.d;
		if (a.c != b.c) return a.c < b.c;
		return a.s < b.s;
		});;

	ll ans = 0;
	for (int i = 0;i < (1 << N); i++)
	{
		ans = max(ans, cache(i));
	}

	cout << ans;

	
	return 0;
}

 

그렇다면 마지막 서브태스크는 dp를 사용하는것일 텐데 고민을하다가 해답코드를 보았다.

https://github.com/E869120/kyopro_educational_90/blob/main/sol/011-03.cpp

주석 step3 부분을 보면 N번째 일을 할지 안할지를 정하는 방식으로 dp를 적용하는것이다.

dp[i][j] 의 경우에 i번째 작업까지 고려했을 때, j일차까지 얻을 수 있는 최대 보상을 의미하는 것 같다.

시간들면 풀어봄직할만한 문제인 것 같긴하다.