AtCoder Educational DP Contest A~E

https://atcoder.jp/contests/dp/tasks

Tasks - Educational DP Contest

 

A. 

i에서 i+1 or i+2로 전이할 수 있습니다. 즉 i는 i-1과 i-2에서 옵니다. 

dp[i]=max(dp[i-1]+C1 , dp[i-2]+C2) 임을 쉽게 알 수 있습니다. 

시간복잡도는 O(N)입니다. 

#include<bits/stdc++.h>
using namespace std;
int n, h[100005], dp[100005];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> h[i];
	fill(&dp[0], &dp[n + 1], 1e9);
	dp[1] = 0;
	dp[2] = abs(h[2] - h[1]);
	for (int i = 3; i <= n; i++) {
		dp[i] = min(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
		dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
	}
	cout << dp[n] << '\n';
}

 

 

B. 

i에서 i+1~i+k로 전이할 수 있습니다. 즉 i는 i-k ~ i-1에서 옵니다. 

dp[i]를 i번까지 최소 비용이라 하면, dp[i]=max(dp[i-j]+C) 꼴입니다. 

시간복잡도는 O(NK)입니다.

#include<bits/stdc++.h>
using namespace std;
int n, k, h[100005], dp[100005];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)cin >> h[i];
	fill(&dp[0], &dp[n + 1], 1e9);
	dp[1] = 0;
	dp[2] = abs(h[2] - h[1]);
	for (int i = 3; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (i>j) dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));

		}
	}
	cout << dp[n] << '\n';
}

 

 

C. 

연속되게 같은 선택을 할 수 없습니다. 탑다운식 DP는 이미 고려된 경우의 수보다는

앞으로 고려할 것을 선택하게끔 DP를 정의해주는게 편합니다. 전이시 필요한 조건은

현재 인덱스(사실 필요없음)와 제일 마지막에 선택한게 무엇인지 입니다.  

go(i, j)를  i번을 고려할 것이고, 제일 마지막에 택한게 j일 때 최댓값이라고 정의합니다. 

여기서 j=0,1,2이며 세가지 선택을 나타냅니다. 

go(i,j)는 k!=j에 대해 go(i+1,k)+val 꼴로 전이됩니다. 최종답은 뭐부터 시작해도 상관없으므로

max(go(0,0), go(0,1), go(0,2))가 됩니다. 

#include<bits/stdc++.h>
using namespace std;
int n, a[100005][3], dp[100005][3];

int go(int i, int j) {
	if (i == n) return 0;
	int& ret = dp[i][j];
	if (~ret) return ret;
	for (int k = 0; k < 3; k++) {
		if (k != j) {
			ret = max(ret, go(i + 1, k) + a[i][k]);
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	}
	memset(dp, -1, sizeof(dp));
	cout << max({ go(0, 0), go(0, 1), go(0, 2) }) << '\n';
}

 

 

D. 

냅색 DP입니다. dp[i][j]를 i번까지 봤을 때 무게가 j일 때 최대 가치라고 정의합니다. 

dp[i][j]=max(dp[i-1][j-w[i]]+v[i])임을 알 수 있습니다. 여기서 최적화해봅시다. 

1번씩만 고르므로 뒤에서부터 순회해주면 무조건 1번씩 고르게 됩니다. 

반대로 앞에서부터 j를 갱신시키면 중복해서 골라지는 경우가 발생하게 됩니다. 

따라서 j를 반대로 순회하면 dp[j]=max(dp[j-w]+v)꼴로 O(N)에 풀어줄 수 있습니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, W, w[111], v[111];
ll dp[100001];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> W;
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = W; j>=w[i]; j--) {
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
	}
	cout << dp[W];
}

 

 

E. 

이번엔 D와 달리 W가 너무 크므로 무게에 대한 점화식을 세울 수 없습니다. 

다만 V가 작습니다. dp[i][j]를 i번까지 봤을 때 가치가 j일 때 무게의 최솟값이라 정의합니다. 

dp[i][j]=min(dp[i-1][j-v]+w)꼴임을 알 수 있습니다. 이제 순회하면서 만약 dp[i][j]<W라면 j를 가능한 크게

갱신해주면 됩니다. j의 최대는 1e5이므로 O(1e5*100)은 충분한 시간이 됩니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, W, w[111], v[111];
ll dp[2][111111];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> W;
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i];
	}
	ll ans = 0;
	fill(&dp[0][0], &dp[1][100001], 1e18);
	dp[0][0] = 0;
	for (ll i = 1; i <= n; i++) {
		for (ll j = 0; j <= 100000; j++) {
			dp[i&1][j] = dp[(i - 1)&1][j];
			if (j >= v[i]) {
				dp[i&1][j] = min(dp[i&1][j], dp[(i - 1)&1][j - v[i]] + w[i]);
			}
			if (dp[i&1][j] <= W) ans = max(ans, j);
		}
	}
	cout << ans << '\n';
}