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

树形dp问题

dfs解决树形dp

UVALive4472

dp(u)=∑inumdp(vi)num=sizeu⋅T−1100+1 ans=dp(0)\begin{gathered} dp(u) = \sum_i^{num}dp(v_i) \\ num = \frac{size_u\cdot T-1}{100} + 1 \\ \ \\ ans = dp(0) \end{gathered} 

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

本例中加判唯一性

{d(u,1)=∑v∈son(u)d(v,0)f(u,1)={⋂v∈son(u)f(v,0)==1}\begin{cases} d(u, 1) = \sum_{v \in son(u)} d(v, 0) \\ f(u, 1) = \{\bigcap_{v \in son(u)} f(v, 0)==1\} \end{cases}

{d(u,0)=max⁡v∈son(u){d(v,1),d(v,0)}f(u,0)=0∀v∈son(u),d(v,0)=d(v,1)f(u,0)=0∀v∈son(u),k∈{0,1},d(v,k)>d(v,k⊕1),f(v,k)=0\begin{cases} d(u, 0) = \max_{v \in son(u)} \{d(v, 1), d(v, 0)\} \\ f(u, 0) = 0 && \forall v\in son(u), d(v, 0)=d(v,1) \\ f(u, 0)= 0 && \forall v \in son(u), k \in \{0,1\}, d(v, k)>d(v, k\oplus 1), f(v, k)=0 \end{cases}

st:d(maxn,2)←0,f(maxn,2)←0\textbf{st}: d(maxn, 2) \leftarrow 0, f(maxn, 2) \leftarrow 0
ed:max⁡(dp(0,1),dp(0,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

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

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

A1↔A2,A1 拿出去 x1 个元素，从 A2 处获得 x2 个元素A_1 \leftrightarrow A_2, \quad A_1 \text{ 拿出去 } x_1 \text{ 个元素，从 } A_2 \text{ 处获得 } x_2 \text{ 个元素}

x1=C0=0x_1 = C_0 = 0
A1−x1+x2=M⇒x2−x1=M−A1=C1A_1-x_1+x_2 = M \quad\Rightarrow x_2-x_1= M-A_1 = C_1
A2−x2+x3=M⇒x3−x2=M−A2=C2A_2-x_2+x_3 = M \quad\Rightarrow x_3-x_2= M-A_2 = C_2
⋯⋯\cdots \cdots
xi−xi−1=M−Ai−1=Ci−1x_i - x_{i-1} = M-A_{i-1} = C_{i-1}

CiC_i 构成了差分序列，根据差分序列的前缀和等于原序列

xi=∑j=1i−1Cjx_i= \sum_{j = 1}^{i-1}C_j

可以根据 CC 的前缀和直接得到
[x1,x2,⋯ ,xn][x_1, x_2, \cdots, x_n]

这样问题就转换为
∀i,j,i≠j,∑∣xi−xj∣\forall i, j, \quad i \neq j, \quad \sum|x_i-x_j| 最小
这个问题可以用中位数模型，排序后，mid=x[n/2]mid=x[n/2]
ans=∑i=1n∣xi−mid∣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

pi=in⋅1=i(n+m)n(n+m) qi=in+m⋅1=inn(n+m) Δ=∣pi−qi∣=∣in⋅(n+m)−i⋅nn∣(n+m)\begin{gathered} p_i = \frac{i}{n}\cdot 1 = \frac{i(n+m)}{n(n+m)} \\ \ \\ q_i = \frac{i}{n+m}\cdot 1 = \frac{in}{n(n+m)} \\ \ \\ \Delta = |p_i-q_i| = \frac{|\frac{i}{n}\cdot (n+m) - i\cdot\frac{n}{n}|}{(n+m)} \end{gathered}

∣in⋅(n+m)−i⋅nn∣ 求的是 in⋅(m) 和距离它最近的整数的距离\begin{gathered} |\frac{i}{n}\cdot (n+m)-i \cdot \frac{n}{n}| \text{ 求的是}\\ \ \\ \frac{i}{n} \cdot (m) \text{ 和距离它最近的整数的距离} \end{gathered}

归一化之后，floor(x+0.5)\textbf{floor}(x+0.5) 表示 xx 四舍五入之后的值
ans=∣x−floor(x+0.5)∣ans = |x - \textbf{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);
    }
}