动态规划综合（三）

本文重点讲一下状态压缩类dp
和复杂状态下的动态规划问题处理方法

状态压缩dp

最优配对问题

最优配对问题
空间里有 $n$ 个点 $P_0, P_1, \cdots, P_{n-1}$
将他们配对成 $\frac{n}{2}$ 对, 使得每个点恰好在一个点对中
所有点对中的两点距离之和尽量小

先写出状态转移方程
以配对的点作为 $dp$ 的阶段
当前已经配对了 $i-1$ 个点, 正在配对第 $i$ 个点

可以用状态压缩的方法, 当前点在不在集合 $S$ 中, 可以用二进制表示

$\begin{gathered} d(i, S) \xleftarrow{\min} d(i-1, S-\{i\}-\{j\})+ |P_iP_j| \\ \ \\ d(i, S) = \min_{j \in [0, i-1]} \{|P_iP_j|+d(i-1, S-\{i\}-\{j\})\} \end{gathered}$


void initdp() {
    memset(d, -inf, sizeof(d));
    d[0][0] = 0;
}

void dp() {
    for(int i = 0; i < n; i++) {
        for(int S = 0; S < (1<<n); S++) {
            for(int j = 0; j < i; j++) if(S & (1<<j)) 
                d[i][S] = max(d[i][S], dist(i, j) + d[i-1][S^(1<<i)^(1<<j)]);
        }
    }
}

然后可以对代码进行等价变形
$i$ 是 $S$ 中第一个不为 $0$ 的位
也就是说, 第一个存在于 $\textbf{S}$ 中的元素
$j \in [i+1, n)$

void dp() {
    for(int S = 0; S < (1<<n); S++) {
        int i, j;
        for(i = 0; i < n; i++) if(S & (1<<i))
            break;
        for(j = i + 1; j < n; j++)
            if(S & (1<<j)) D[S] = max(D[S], dist(i, j) + D[S^(1<<i)^(1<<j)]);
    }
}

TSP问题

$n$ 个城市, 两两有道路相连, 给出两个城市 $i, j$ 的道路长度 $L(i, j)$
求一条经过每个城市仅一次, 最后回到起点的路线, 使得经过的道路总长度最短

这个问题仍然可以用一个状态压缩表示集合
当前 $dp$ 的阶段是决策点 $i$
已经加入决策的集合, 就是已经路过的点构成集合 $S$

$d(i, S)=\min_{j \in S} \{d(j, S-\{i\}) +dist(i,j)\}$

$\begin{gathered} \textbf{st:} \ \textbf{for} \ \forall i, \quad d(i, \{\})=dist(0, i) \\ \ \\ \textbf{ed:} \ \quad d(0, \{1, 2, \cdots, n-1\}) \end{gathered}$

图的色数

给一个无向图 $G$ , 把图中的节点染成尽量少的颜色, 使得相邻节点的颜色不同

用当前已经在集合 $S$ 中的节点数作为 $dp$ 的阶段
$d(S)$ 表示当前节点集 $S$ 最少用了多少种颜色？

$\exists S' \subseteq S, S'$ 是可以染成同一种颜色的节点集
根据条件, $S'$ 必然是个独立点集, $S'$ 中的节点没有边相连

$\begin{gathered} color\{S-S'\} + color(S') \\ \ \\ d(S) = \min\{d(S-S') + 1\} \end{gathered}$

$dp$ 实现的时候可以枚举子集

d[0] = 0;
for(int S = 1; S < (1<<n); S++) {
    d[S] = inf;
    for(int S0 = S; S0; S0 = (S0-1) & S) {
        if(no_edges_inside(S0)) d[S] = min(d[S], d[S-S0] + 1);
    }
}

状态压缩dp实践

$dp$ 问题很重要的一点是阶段的划分
$\textbf{dp}$ 阶段一般取独立变量, 什么意思呢？
比如有 $n$ 个点, $P_1, P_2, \cdots, P_n$
$\forall i, j \in [1, n],$ 任意两个点 $P_i, P_j$
决策集合互不影响, 也就是说
决策 $P_i$ 的时候, 并不会影响到 $P_j$

举个例子, 上述最优配对问题中, $(P_{i1}, P_{j1})$ 的配对
并不会影响 $(P_{i2}, P_{j2})$ 的配对, 相对独立

在图的色数问题中, 如果用节点作为决策阶段,
$P_i$ 的染色情况, 会影响到 $P_j$ 染色情况, 如果 $(i, j)$ 有边相连
二者有约束, 不是相对独立的

状态压缩例1

UVA10817

很显然根据前面的分析, 应该用 $\text{check}$ 到第 $i$ 个教师作为 $dp$ 阶段
状态维度1
$i \in [0, m-1]$ , 不能辞退
$i \in [m, m+n-1]$ 可以辞退, 也就是说, 存在两种状态, 聘用 $\textbf{or}$ 不聘用

状态维度2
$S_1$ 是 $0, 1$ 集合, 表示恰好有一个人教的科目的集合
$S_2$ 表示至少有 $2$ 个人教的科目的集合
$S_0$ 表示总状态, 可以理解为没有任何人教的科目的集合
$st\rightarrow ed: \quad S_0: ((1<<n)-1) \longrightarrow 0$

状态计算

$\begin{gathered} d(i, S_1, S_2) = \min\{d(i+1, S_1, S_2), d(i+1, S_1', S_2')+C[i]\} \\ \ \\ (S_1, S_2) \xrightarrow{\textbf{check} \ ith} (S_1',S_2') \end{gathered}$

注意, 只有在 $i \geqslant m$ 时才出现第二项
如果把第 $i$ 个人能够教的科目状态记为 $st[i]$

从没人教的科目 $S_0$ 集合中, 选出第 $i$ 个人能够教的科目
$v1 \leftarrow S_0 \ \textbf{and} \ st[i]$
已经有 $1$ 个人教的科目集合中, 第 $i$ 个人还可以教的科目集合
$v2 \leftarrow S_1 \ \textbf{and} \ st[i]$ , 为计算 $S_2$ 做准备

$S_0' = S_0 \oplus v1$
$S_1' = (S_1 \oplus v2) \ \textbf{or} \ v1$
$S_2' = S_2 \ \textbf{or} \ v2$

dp的起始状态
这里是从 $n\rightarrow 1$ 递推
表示安排了几个老师？
$\textbf{start}:\quad dp(0, (1<<s)-1, 0, 0)$
$\textbf{end}: \quad s_2 = (1<<s)-1, dp() = 0$

const int maxs = 8;
const int maxn = 100 + 20 + 5;
const int inf = 0x3f3f3f3f;

int m, n, s;
int st[maxn], c[maxn];

int d[maxn][(1<<maxs)+1][(1<<maxs)+1];

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

int dp(int i, int s0, int s1, int s2) {
    if(i == m + n) return s2 == (1<<s)-1 ? 0 : inf;
    int& ans = d[i][s1][s2];

    if(ans >= 0) return ans >= inf ? inf : ans;

    ans = inf;
    if(i >= m) ans = dp(i+1, s0, s1, s2);

    int v1 = s0 & st[i], v2 = s1 & st[i];
    s0 ^= v1;
    s1 = (s1 ^ v2) | v1;
    s2 |= v2;

    ans = min(ans, dp(i+1, s0, s1, s2) + c[i]);

    return ans;
}


int main() {
    freopen("input.txt", "r", stdin);
    string line;
    while (getline(cin, line)) {
        stringstream ss(line);
        ss >> s >> m >> n;
        if(s == 0) break;

        _for(i, 0, n + m) {
            getline(cin, line);
            stringstream ss(line);

            ss >> c[i];
            int x;
            st[i] = 0;
            while (ss >> x) {
                x--;
                st[i] |= (1<<x);
            }
        }

        // input finished
        // dp

        initdp();
        int ans = dp(0, (1<<s)-1, 0, 0);
        printf("%d\n", ans);
    }
}

状态压缩例2

UVALive4643

假设心里想的物品是 $\textbf{Item}$
可以发现, 对于特征 $\forall k \in [1, m]$ 是相对独立的
可以作为 $dp$ 的阶段

每一个特征都有2种状态, 表示存在与否, 很容易想到用状态压缩

$\textbf{algorithm}$ 状态表示和状态转移
假设当前问询特征 $k$ , 特征 $[1, \cdots, k-1]$ 构成状态集合 $S$
其中集合 $S$ 中 $\text{ Item }$ 已经确定（已经拥有）的特征集合是 $q$
$q\subseteq S,\quad d(S, q)$ 表示此时的询问次数

$k$ 这个特征, 有两种状态, $\text{Item }$ 拥有特征 $\textbf{or}$ 不拥有特征

$\begin{gathered} d(S,q) = \max [d(S+\{k\}, q+\{k\}), d(S+\{k\},q)] + 1 \\ \ \\ ans = \min (ans, d(S, q)) \end{gathered}$

$\textbf{algorithm}$ 状态计算, dp边界的确定
上面的状态转移方程, 什么时候可以计算结束了呢？

对于某个状态 $(S, q)$ , 什么时候可以终止递归了呢？

$cnt(S, q) = 1$ 这个状态只包含一个物体
$cnt(S, q) = 0$ 这个状态不包含任何物体
这两种状态都不需要再继续做任何问询, $\textbf{return} \ 0$

$\textbf{if} \ \text{cnt}(S', q') \leqslant 1$
$~~~~~~$ $d(S', q') \ \textbf{return} \ 0$
$~~~~~~$ $d(S, q) = d(S', q') + 1$
$~~~~~~$ $\text{此时只需要问询第 } k \text{ 个特征 } 1 \text{ 次即可知道答案}$

$\textbf{if} \ \text{cnt}(S', q') = 2$
$~~~~~~$ $d(S', q') \ \textbf{return} \ 1$
$~~~~~~$ $d(S, q) = d(S', q') + 1$
$~~~~~~$ $\text{集合中有 2 个元素的话, 需要问询 2 次}$

const int maxs = 11;
const int maxn = 128 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
string obj[maxn];
int cnt[(1<<maxs)+1][(1<<maxs)+1];

void _init() {
    memset(cnt, 0, sizeof(cnt));
}


void getdata() {
    _for(i, 0, n) {
        int features = 0;
        _for(k, 0, obj[i].length()) {
            if(obj[i][k] == '1') features |= (1<<k);
        }

        for(int S = 0; S < (1<<m); S++) cnt[S][S & features]++;
    }
}

int d[(1<<maxs)+1][(1<<maxs)+1];
void initdp() {
    memset(d, -1, sizeof(d));
}

int dp(int S, int q) {
    if(cnt[S][q] <= 1) return 0;
    if(cnt[S][q] == 2) return 1;

    int& ans = d[S][q];
    if(ans != -1) return ans;

    ans = m;
    _for(k, 0, m) {
        if(S & (1<<k)) continue;
        int S2 = S | (1<<k), q2 = q | (1<<k);
        if(cnt[S2][q] >= 1 && cnt[S2][q2] >= 1) {
            int val = max(dp(S2, q2), dp(S2, q)) + 1;
            ans = min(ans, val);
        }
    }

    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &m, &n) == 2 && n) {
        _init();
        _for(i, 0, n) cin >> obj[i];

        // get data
        getdata();

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

指标哈希进行状态压缩

Gym100273F
UVA1412-01
UVA1412-02

用数组指标哈希编码，进行状态压缩时候，常用的技巧
先 $\textbf{dfs}$ 枚举出所有的合法状态，非法状态用 $-1$ 标记
比如本例中，所有合法的状态 $\textbf{buy}(s, i) \geqslant 0$

const double eps = 1e-3;
const int maxstate = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int maxn = 10;
const int maxm = 100 + 10;
double c, price[maxn][maxm];
// price[i][j]  i stock, j day
int n, m, kk, s[maxn], k[maxn];
char name[maxn][10];

vector<vector<int> > states;
vector<int> lots;
map<vector<int>, int> ID;

void dfs(int x, int tot) {
    if (x == n) {
        ID[lots] = states.size();
        states.push_back(lots);
        return;
    }
    for (int cnt = 0; cnt <= k[x] && tot + cnt <= kk; cnt++) {
        lots[x] = cnt;
        dfs(x+1, tot + cnt);
    }
}

void dbg(const int buy[][maxn]) {
    for (int i = 0; i < states.size(); i++) {
        for (int j = 0; j < n; j++) printf("%d ", buy[i][j]);
        printf("\n");
    }
}

int buy[maxstate][maxn], sell[maxstate][maxn];
void prework() {
    states.clear();
    lots.resize(n);
    fill(lots.begin(), lots.end(), 0);
    ID.clear();
    memset(buy, -1, sizeof buy);
    memset(sell, -1, sizeof sell);
    dfs(0, 0);

    for (int S = 0; S < states.size(); S++) {
        int tot = 0;
        for (auto x : states[S]) tot += x;

        for (int i = 0; i < n; i++) {
            // buy or sell stock i, only one stock once
            // eg. buy[S][i] -> ID(newState)
            if (tot + 1 <= kk && states[S][i] + 1 <= k[i]) {
                vector<int> newStates(states[S]);
                newStates[i]++;
                buy[S][i] = ID[newStates];
            }
            if (states[S][i] > 0) {
                vector<int> newStates(states[S]);
                newStates[i]--;
                sell[S][i] = ID[newStates];
            }
        }
    }

    // printf("BUY\n"); dbg(buy);
    // printf("SELL\n"); dbg(sell);
}

double f[maxm][maxstate];
int pre[maxm][maxstate];
int opt[maxm][maxstate];
void update(int day, int s, int s2, double val, int o) {
    if (val > f[day+1][s2]) {
        f[day+1][s2] = val;
        pre[day+1][s2] = s;
        opt[day+1][s2] = o;
    }
}

double dp() {
    memset(f, -inf, sizeof f);
    memset(pre, 0, sizeof pre);
    memset(opt, 0, sizeof opt);

    f[0][0] = c;
    for (int day = 0; day < m; day++) {
        for (int S = 0; S < states.size(); S++) {
            if (f[day][S] < 0-eps) continue;

            update(day, S, S, f[day][S], 0);
            for (int i = 0; i < n; i++) {
                if (buy[S][i] >= 0 && f[day][S] >= price[i][day] - eps) {
                    update(day, S, buy[S][i], f[day][S]-price[i][day], i+1);
                }
                if (sell[S][i] >= 0) {
                    update(day, S, sell[S][i], f[day][S]+price[i][day], -i-1);
                }
            }
        }
    }
    return f[m][0];
}

void out(int day, int S) {
    if (day == 0) return;
    out(day-1, pre[day][S]);
    if (opt[day][S] == 0) printf("HOLD\n");
    else if (opt[day][S] > 0) printf("BUY %s\n", name[ opt[day][S]-1 ]);
    else printf("SELL %s\n", name[ -opt[day][S]-1 ]);

}

int main() {
    freopen("fund.in", "r", stdin);
    freopen("fund.out", "w", stdout);
    int kase = 0;
    while (scanf("%lf%d%d%d", &c, &m, &n, &kk) == 4) {
        if (kase++ > 0) printf("\n");
        // get data
        for (int i = 0; i < n; i++) {
            scanf("%s%d%d", name[i], &s[i], &k[i]);
            for (int j = 0; j < m; j++) {
                scanf("%lf", &price[i][j]);
                price[i][j] *= s[i];
            }
        }
        // prework
        prework();

        // dp
        double res = dp();
        printf("%.2lf\n", res);

        // out
        out(m, 0);
    }
}

动态规划中一些创造性思维

饼干
这个题目也是属于经典问题了
不过这里重点思考一下, 发现

第 $i$ 个孩子分到饼干, 影不影响第 $i+1$ 个孩子?
注意到如果饼干拿到的多, 或者少, 会影响到
$d(i+1) = d(i) + f(i)$
$f(i)$ 会产生一个怨气值, 但注意, 这里不叫影响
这个是第 $i$ 个孩子拿饼干和第 $i+1$ 个孩子那饼干的状态转移
第 $i$ 个孩子拿饼干, 是和第 $i+1$ 个孩子拿到饼干的过程相对独立
也就是说, 第 $i$ 个孩子能拿到饼干, 并不会对第 $i+1$ 个孩子拿到饼干产生影响
第 $i+1$ 个孩子该拿拿, 不该拿就不拿, 和第 $i$ 个孩子无关
$i \in [1, n]$ 可以作为 $\text{dp}$ 的阶段
再看饼干, 假设当前分配了 $j$ 个饼干, 对分配 $j+1$ 个饼干有没有影响？
也是没有的, 第 $j+1$ 个饼干爱怎么分配怎么分配, 爱给谁就给谁

$d(i, j)$ 孩子, 和饼干, 都可以作为 dp 的阶段

类似的问题还有啥？
还有公共子序列问题啊！
$A[i], B[j]$
在公共子序列选择 $A_i$ , 对 $A_{i+1}$ 不会造成影响
同样, 选择 $B_j$ 对 $B_{j+1}$ 也不会造成影响
都是你爱选就选, 不选就拉倒

饼干问题特殊性的说明

饼干这个问题有点特殊, 因为
$f(i) = g(i) \cdot a(i)$
$a(i)$ 取决于相对顺序
取决于相对顺序的问题, 一般情况下都有等效冗余
什么意思呢？

$a_{i} = f(\Delta x_i), \quad \Delta x_i = x_i - x_{i-1}$
我把 $x_i, x_{i-1}$ 都减掉 $t$ ,
$\Delta x_i = (x_i - t) - (x_{i-1} - t)$ 结果是完全不变的
当然前提是 $\textbf{for} \ \forall i , \quad x_i -t > 0$
也就是说, 这个问题的等效状态是