动态规划综合(二)

这篇博文写了一些动态规划的实践问题
$\textbf{树形dp,复杂状态的dp}$

树形dp问题

dfs解决树形dp

UVALive4472

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int N, T;

vector<int> son[maxn];

int dp(int u) {
if(son[u].empty()) return 1;

vector<int> vec;
for(auto v : son[u]) {
vec.push_back(dp(v));
}
sort(vec.begin(), vec.end());

int num = (son[u].size() * T - 1) / 100 + 1;

int ans = 0;
for(int i = 0; i < num; i++) ans += vec[i];
return ans;
}

void init() {
_for(i, 0, maxn) son[i].clear();
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d", &N, &T) == 2 && N) {
init();

_rep(i, 1, N) {
int x;
scanf("%d", &x);
son[x].push_back(i);
}

// then dp
int ans = dp(0);
printf("%d\n", ans);
}
}

树的最大独立集问题

HDU2412

$\textbf{本例中加判唯一性}$

$\textbf{st}: d(maxn, 2) \leftarrow 0, f(maxn, 2) \leftarrow 0$
$\textbf{ed}: \max(dp(0, 1), dp(0, 0))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

const int maxn = 200 + 10;
map<string, int> mp;
int tot = 0;
int n;
vector<int> son[maxn];

int ID(const string& str) {
if(!mp.count(str)) mp[str] = tot++;
return mp[str];
}

int d[maxn][2];
int f[maxn][2];

void initdp() {
Set(d, 0);
Set(f, 0);
}

int dp(int u, int k) {
d[u][k] = k;
f[u][k] = 1;
for(auto v : son[u]) {
if(k == 1) {
d[u][k] += dp(v, 0);
f[u][k] &= f[v][0];
}
else {
d[u][k] += max(dp(v, 0), dp(v, 1));
if(d[v][0] == d[v][1]) f[u][k] = 0;
else if(d[v][0] > d[v][1] && f[v][0] == 0) f[u][k] = 0;
else if(d[v][1] > d[v][0] && f[v][1] == 0) f[u][k] = 0;
}
}

return d[u][k];
}

void init() {
mp.clear();
tot = 0;

_for(i, 0, maxn) son[i].clear();
}

int main() {
freopen("input.txt", "r", stdin);
string s, s2;
while (cin >> n >> s) {
init();

ID(s);
_for(i, 1, n) {
cin >> s2 >> s;
son[ID(s)].push_back(ID(s2));
}

// then dp
initdp();
int ans = max(dp(0, 1), dp(0, 0));
printf("%d ", ans);

bool flag = true;
if(d[0][0] == d[0][1]) flag = false;
else if(d[0][1] > d[0][0] && f[0][1] == 0) flag = false;
else if(d[0][0] > d[0][1] && f[0][0] == 0) flag = false;

flag == 0 ? printf("No\n") : printf("Yes\n");
}
}

树形dp节点状态

LA3685
POJ3398

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n;
vector<int> G[maxn];

inline void add(int u, int v) {
G[u].push_back(v);
}

// == dp ==
int d[maxn][3];

void initdp() {
memset(d, -1, sizeof(d));

vector<int> ed;
_rep(i, 1, n) if(G[i].size() == 0) ed.push_back(i);

for(auto x : ed) {
d[x][0] = 1;
d[x][1] = 0;
d[x][2] = inf;
}
}

int dp(int u, int pa, int k) {
if(d[u][k] != -1) {
return d[u][k];
}

d[u][0] = 1;
d[u][1] = 0;

for(auto v : G[u]) {
if(v == pa) continue;

d[u][0] += min(dp(v, u, 0), dp(v, u, 1));
d[u][1] += dp(v, u, 2);

if (d[u][0] > inf) d[u][0] = inf;
if (d[u][1] > inf) d[u][1] = inf;

}

d[u][2] = inf;
for(auto v : G[u]) {
if(v == pa) continue;

d[u][2] = min(d[u][2], d[u][1] - dp(v, u, 2) + dp(v, u, 0));
}

return d[u][k];
}

// == dp finished ==

void init() {
_for(i, 0, maxn) G[i].clear();
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d", &n) == 1) {
init();

// get data
_for(i, 0, n - 1) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
// get data finished

initdp();
int ans = min(dp(1, 0, 0), dp(1, 0, 2));
printf("%d\n", ans);
scanf("%d", &n);
}
}

算法设计策略

中位数和差分序列

UVA11300

$\textbf{algorithm}$
$\text{本例子的问题是,一个序列,通过平均分配}$
$\text{使得这个序列最后的值都相等,问 } \sum(\Delta) \text{ 最小值是多少}$

$M = tot / n \text{ 表示最后的值}$
$\text{原序列是 } A_{i}, \text{ 无论如何变化,最后的方案都可以看成是}$
$\text{相邻两项 “转手”}$

$A_1 \leftrightarrow A_2, \quad A_1 \text{ 拿出去 } x_1 \text{ 个元素,从 } A_2 \text{ 处获得 } x_2 \text{ 个元素}$

$x_1 = C_0 = 0$
$A_1-x_1+x_2 = M \quad\Rightarrow x_2-x_1= M-A_1 = C_1$
$A_2-x_2+x_3 = M \quad\Rightarrow x_3-x_2= M-A_2 = C_2$
$\cdots \cdots$
$x_i - x_{i-1} = M-A_{i-1} = C_{i-1}$

$C_i \text{ 构成了差分序列,根据差分序列的前缀和等于原序列}$

$x_i= \sum_{j = 1}^{i-1}C_j$

$\text{可以根据 }C \text{ 的前缀和直接得到 }$
$[x_1, x_2, \cdots, x_n]$

$\textbf{这样问题就转换为}$
$\forall i, j, \quad i \neq j, \quad \sum|x_i-x_j| \text{ 最小}$
$这个问题可以用中位数模型,排序后,mid=x[n/2]$
$ans = \sum_{i = 1}^{n}|x_i - mid|$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int maxn = 1e6 + 10;
ll C[maxn], M = 0;
ll A[maxn];
int n;

void init() {
memset(C, 0, sizeof(C));
}

int main() {
//freopen("input.txt", "r", stdin);
while (scanf("%d", &n) == 1) {
init();
ll tot = 0;

_rep(i, 1, n) {
scanf("%lld", &A[i]);
tot += A[i];
}

M = tot / n;
_for(i, 1, n) C[i] = C[i - 1] + 1ll * M - A[i];

sort(C, C + n);

ll mid = C[n>>1];
ll ans = 0;
_for(i, 0, n) ans += abs(C[i] - mid);
printf("%lld\n", ans);
}
}

精度运算的一些技巧

UVA1388

$\text{归一化之后,floor}(x+0.5) \text{ 表示 x 四舍五入之后的值}$
$ans = |x - floor(x+0.5)|$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int L = 1e4;
int n, m;

int main() {
//freopen("input.txt", "r", stdin);
while (scanf("%d%d", &n, &m) == 2) {
double ans = 0.0;
_for(i, 0, n) {
double x = (double)i / n * (m);
ans += fabs(x - floor(x+0.5)) / (n + m);
}
printf("%.4lf\n", ans * L);
}
}