DP Codeforces Round #322 (Div. 2) F. Zublicanes and Mumocrates

2117 단어 dp
트리 dp, 뿌리 노드의 상태를 기록하면 됩니다...
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 5005;
const int maxm = 10005;
const int INF = 0x3f3f3f3f;

struct Edge
{
	int v;
	Edge *next;
}E[maxm], *H[maxn], *edges;

int dp[maxn][2][maxn];
int size[maxn];
int c[2][maxn];
int lef[maxn];
int du[maxn];
int n;

void addedges(int u, int v)
{
	edges->v = v;
	edges->next = H[u];
	H[u] = edges++;
}

void init()
{
	edges = E;
	memset(H, 0, sizeof H);
	memset(dp, INF, sizeof dp);
}

void debug(int u)
{
	printf("*************************** %d
", u); for(int i = 0; i <= size[u]; i++) printf("PP %d %d %d
", i, dp[u][0][i], dp[u][1][i]); } void dfs(int u, int fa) { if(size[u] == 1) dp[u][0][1] = 0, dp[u][1][0] = 0; else dp[u][0][0] = dp[u][1][0] = 0; for(Edge *e = H[u]; e; e = e->next) if(e->v != fa) { int v = e->v; dfs(v, u); for(int i = 0; i <= size[u] + size[v]; i++) c[0][i] = c[1][i] = INF; for(int i = 0; i <= size[u]; i++) { for(int j = 0; j <= size[v]; j++) { c[0][i + j] = min(c[0][i + j], dp[u][0][i] + dp[v][0][j]); c[1][i + j] = min(c[1][i + j], dp[u][1][i] + dp[v][1][j]); c[0][i + j] = min(c[0][i + j], dp[u][0][i] + dp[v][1][j] + 1); c[1][i + j] = min(c[1][i + j], dp[u][1][i] + dp[v][0][j] + 1); } //c[i + size[v]] = min(c[i + size[v]], dp[u][i]); //c[abs(i - size[v])] = min(c[abs(i - size[v])], dp[u][i] + 1); } size[u] += size[v]; for(int i = 0; i <= size[u]; i++) dp[u][0][i] = c[0][i], dp[u][1][i] = c[1][i]; } //debug(u); } void work() { for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); addedges(u, v); addedges(v, u); du[u]++; du[v]++; } int o, cnt = 0; for(int i = 1; i <= n; i++) { if(du[i] == 1) size[i] = 1, cnt++; else o = i; } dfs(o, 0); printf("%d
", min(dp[o][0][cnt / 2], dp[o][1][cnt / 2])); } int main() { //freopen("data", "r", stdin); while(scanf("%d", &n) != EOF) { init(); work(); } return 0; }

좋은 웹페이지 즐겨찾기