AtCoder Educational DP Contest M~Q

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

Tasks - Educational DP Contest

 

 

M.

dp[i][j]를 i번째 학생까지 합이 j가 되게 나눠주는 경우의 수라고 정의합니다.

dp[i][j]는 dp[i-1][j-k]들의 합입니다. (k=0 ~ a[i]) 

이 식을 navie 하게 계산하면 O(NK^2)입니다. 

dp[i][j]들의 합을 미리 계산해놓아 k=0~a[i]까지 합을 O(1)에 구할 수 있습니다.

그리고 dp식을 갱신할 때 i와 i-1은 반복문 순서 외에는 식에 필요한 역할이 없습니다.

즉, dp[j]들로만 식을 만들면서 dp table을 갱신해주면 더 빠르고 간단하게 구현할 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
const ll mod = 1e9 + 7;
ll n, k, a[101];
ll dp[100001], psum[100001];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)cin >> a[i];
	fill(&dp[0], &dp[a[1] + 1], 1);
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			psum[j] = (j ? psum[j - 1] : 0) + dp[j];
			psum[j] %= mod;
		}
		for (int j = 0; j <= k; j++) {
			ll tmp = (j >= a[i] + 1 ? psum[j - a[i] - 1] : 0);
			dp[j] = (psum[j] - tmp + mod) % mod;
		}
	}
	cout << dp[k] << '\n';
}

 

 

 

N.

파일합치기 문제와 동일합니다. 풀이는 https://hellojaehoon.tistory.com/20 에 있습니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
const ll mod = 1e9 + 7;
ll n, k, x, psum[404];
ll dp[404][404];

ll go(int s, int e) {
	if (s == e) return 0;
	ll& ret = dp[s][e];
	if (~ret) return ret;
	ret = 1e18;
	for (int m = s; m < e; m++) {
		ret = min(ret, go(s, m) + go(m + 1, e) + psum[e] - psum[s - 1]);
	}
	return ret;
}

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

 

 

 

O.

N<=20이므로 bit dp를 의심해봅시다. 1번씩만 쌍을 만들 수 있으므로 방문상태를 

만들어주는 dp가 맞는 것 같네요. 

dp[i][s]를 i번을 채울 것이고, 현재 상태가 s인 경우의 수라고 정의합니다.

dp[i][s]는 모든 j  ∈ g[i] 에 대해 dp[i+1][s|1<<j] 들의 합이 됩니다. 

총 경우의 수는 마지막에 채우는 상태가 2^n-1 이면 1을 리턴해줍니다. 

답은 dp[0][0]이 됩니다. 이거로도 AC지만 최적화를 해봅시다. 

어차피 처음부터 순차적으로 채워도 답에는 변함이 없으므로 

0번부터 매칭시키면 i번을 채울 것이라는 인덱스는 필요없습니다.

근데 그럼 i를 모르니 j  ∈ g[i]인 j를 못찾는데..? 하지만 상태 s를 잘 봅시다.

s에서 1의 개수가 지금까지 채운 개수입니다. 즉 다음에 채울 인덱스는 s의 1의 개수가 됩니다. 

따라서 1차원 dp로도 충분히 가능합니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, dp[1 << 22];
const ll mod = 1e9 + 7;
vector<int>g[21];

ll go(int state) {
	int i = __builtin_popcount(state);
	if (i == n) return 1;
	ll& ret = dp[state];
	if (~ret) return ret;
	ret = 0;
	for (int j : g[i]) {
		if (state & (1 << j))continue;
		ret += go(state | (1 << j));
		ret %= mod;
	}
	return ret;
}

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

 

 

 

P.

트리 dp의 기본문제네요.

dp[i][c]를 i번을 색 c로 칠하는 경우의 수라고 합니다. (0: 흰색, 1: 검은 색)

c=0이면 dp[child][0]+dp[child][1]들을 곱해주면 됩니다.

c=1이면 dp[child][0]만 가능합니다. 리프노드일 때 1을 리턴해주면 됩니다.

답은 dp[1][0]+dp[1][1]이 됩니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
ll n, u, v, dp[100005][2];
const ll mod = 1e9 + 7;
vector<int>g[100005];

ll go(int cur, int c, int prev) {
	ll& ret = dp[cur][c];
	if (~ret) return ret;
	ret = 1;
	for (int nxt : g[cur]) {
		if (nxt == prev) continue;
		if (c == 0) {
			ret *= (go(nxt, 0, cur) + go(nxt, 1, cur)) % mod;
			ret %= mod;
		}
		else {
			ret *= go(nxt, 0, cur);
			ret %= mod;
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i < n; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cout << (go(1, 0, -1) + go(1, 1, -1)) % mod << '\n';
}

 

 

 

 

Q. 

dp[i]를 i번을 사용했을 때 지금까지 아름다움의 최댓값이라 정의합니다.

dp[i]=max(dp[j])+a[i]입니다. 단, j는 hj<hi를 만족하고 j<i 역시 만족해야 합니다.

이런 j를 naive하게 찾아주면 O(N^2)입니다. 세그먼트 트리로 줄여줄 수 있습니다. 

dp값을 채우고 세그트리의 h[i] 인덱스에 dp값을 갱신해놓습니다.

그럼 j를 찾을 때 당연히 j<i는 만족되고 hj<hi를 만족하는 dp의 최댓값은 

구간 [1, hi-1]에서 최댓값입니다. 따라서 O(NlogN)으로 줄여줄 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
const int MAX = 200005;
ll n, h[MAX], a[MAX];
ll tree[4*MAX], ans;

void upd(int node, int s, int e, int idx, ll v) {
	if (idx < s || idx > e) return;
	if (s == e) {
		tree[node] += v;
		return;
	}
	int m = s + e >> 1;
	upd(2 * node, s, m, idx, v);
	upd(2 * node + 1, m + 1, e, idx, v);
	tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

ll query(int node, int s, int e, int qs, int qe) {
	if (s > qe || e < qs) return 0;
	if (qs <= s && e <= qe) return tree[node];
	int m = (s + e) >> 1;
	ll q1 = query(2 * node, s, m, qs, qe);
	ll q2 = query(2 * node + 1, m + 1, e, qs, qe);
	return max(q1, q2);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> h[i];
	for (int i = 1; i <= n; i++)cin >> a[i];
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ll temp = query(1, 1, MAX, 1, h[i] - 1);
		ans = max(ans, temp + a[i]);
		upd(1, 1, MAX, h[i], temp + a[i]);
	}
	cout << ans << '\n';
}