Regionals 2014 >> Asia - Taichung 7003 - A Balance Game on Trees 树形DP + 二维费用背包

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5015

设dp[cur][i][j]表示当前是第cur个顶点,自身状态是i(0或者1),爸爸的状态是j(0或者1)的时候的最多白色节点数。

0---白色

1---黑色

如果不合法,就是第cur号顶点不能染成白色,则为-1,注意到任意节点都可以染成黑色,所以dp[cur][1][0] = dp[cur][1][1] = 0

转移:

首先把叶子节点特判掉,因为叶子节点的状态很容易判断,并且只有k == 1的时候,才有dp[left][0][1] = 1

然后留给每一个爸爸的转移就是:

1、如果爸爸染黑色,则从  dp[son][1][1]和dp[son][0][1]娶个max过来即可。

2、比较麻烦的是爸爸染了白色。这样就相当于对于所有的儿子(儿子的状态已经全部算出来了),把k个染成黑色(使得爸爸合法),剩下的染成白色,使得白色节点数最大,

也就是给出一个结构体数组,有arr[i].a和arr[i].b表示这个节点染成白色,得到arr[i].a贡献,这个节点染成黑色,得到arr[i].b贡献。

设d[n][k]表示前n个物品,确定选了k个做黑色的最大贡献。二维费用背包转移即可。hack: 需要用到d[i][0]

所以d[0][0] = 0,而d[1][0] = arr[1].a    d[2][0] = arr[1].a + arr[2].a

这题写那个二维费用dp的时候坑队友了,没写出来,转移的时候没考虑d[i][0]

#include <bits/stdc++.h>
#include <algorithm>
#define inf (0x3f3f3f3f)
using namespace std;
typedef long long int LL;
const int maxn = 1e2 + ;
int dp[maxn][][];
char str[ + ];
struct Edge {
int u, v, tonext;
} e[maxn * ];
int first[maxn], num;
void addEdge(int u, int v) {
e[num].u = u, e[num].v = v, e[num].tonext = first[u];
first[u] = num++;
}
int son[maxn];
bool in[maxn];
int n, k; void show() {
for (int i = ; i <= n; ++i) {
printf("node %d: ", i);
for (int j = first[i]; ~j; j = e[j].tonext) {
printf("%d ", e[j].v);
}
printf("\n");
}
printf("***************\n");
}
vector<int> vc[maxn];
int d[maxn][];
struct Node {
int a, b;
Node(int _a, int _b) {
a = _a, b = _b;
}
Node() {}
} arr[maxn];
int getMax(struct Node arr[], int n, int k) {
if (k < ) return -inf;
if (k == ) {
int sum = ;
for (int i = ; i <= n; ++i) sum += arr[i].a;
return sum;
}
if (n < k) return -inf;
memset(d, -0x3f, sizeof d);
d[][] = ;
for (int i = ; i <= n; ++i) {
for (int j = k; j >= ; --j) {
if (d[i - ][j] >= ) d[i][j] = max(d[i][j], d[i - ][j] + arr[i].a);
if (j >= && d[i - ][j - ] >= ) d[i][j] = max(d[i][j], d[i - ][j - ] + arr[i].b);
}
}
return d[n][k];
}
void dfs(int cur) {
if (!son[cur]) return;
for (int i = first[cur]; ~i; i = e[i].tonext) {
int v = e[i].v;
vc[cur].push_back(v);
dfs(v);
dp[cur][][] += max(dp[v][][], dp[v][][]);
dp[cur][][] += max(dp[v][][], dp[v][][]); // 爸爸是黑色
}
int sel = , val = , to = ;
for (int i = ; i < vc[cur].size(); ++i) {
int v = vc[cur][i];
if (dp[v][][] >= ) {
arr[++to] = Node(dp[v][][], dp[v][][]);
} else {
sel++; //这些不能变成白色,也就是固定必须是黑色
val += dp[v][][]; //其贡献
}
}
dp[cur][][] = getMax(arr, to, k - - sel) + val;
dp[cur][][] = getMax(arr, to, k - sel) + val;
if (dp[cur][][] < ) dp[cur][][] = -;
else dp[cur][][]++;
if (dp[cur][][] < ) dp[cur][][] = -;
else dp[cur][][]++;
}
void work() {
num = ;
memset(in ,false, sizeof in);
memset(first, -, sizeof first);
memset(dp, -, sizeof dp);
memset(son, false, sizeof son);
scanf("%d%d", &n, &k);
for (int i = ; i <= maxn - ; ++i) vc[i].clear();
getchar();
for (int i = ; i <= n; ++i) {
gets(str + );
// printf("%s\n", str + 1);
int lenstr = strlen(str + );
for (int j = ; j <= lenstr;) {
if (str[j] >= '' && str[j] <= '') {
int fuck = str[j] - '';
++j;
while (j <= lenstr && str[j] >= '' && str[j] <= '') {
fuck = fuck * + str[j] - '';
++j;
}
if (fuck == ) break;
son[i]++;
addEdge(i, fuck);
in[fuck] = true;
} else j++;
}
}
int root = ;
for (int i = ; i <= n; ++i) {
if (!in[i]) {
root = i;
break;
}
}
// show();
if (n == ) {
if (k != ) {
printf("0\n");
return;
}
}
for (int i = ; i <= n; ++i) {
dp[i][][] = dp[i][][] = ;
}
if (k == ) {
printf("%d\n", n);
return;
}
if (k == ) {
for (int i = ; i <= n; ++i) {
if (!son[i]) {
dp[i][][] = ;
dp[i][][] = -;
dp[i][][] = ;
dp[i][][] = ;
}
}
}
dfs(root);
int ans = dp[root][][];
ans = max(ans, dp[root][][]);
ans = max(ans, dp[root][][]);
// ans = max(ans, dp[root][0][1]);
printf("%d\n", ans);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
上一篇:Javascript学习笔记——操作浏览器对象


下一篇:【Seajs源码分析】3. 工具方法2