Problem

水题

LuoguP1472 奶牛家谱 Cow Pedigrees

题意：有$n$个结点$k$层的二叉树结构个数，树只能有$2$个儿子或$0$个儿子。

设$dp[n][k]$为有$n$个结点不到$k$层的答案，则答案容斥一下为$dp[n][k]-dp[n][k-1]$，转移从下把两棵树连接到上一层结点，枚举$t$为左子树节点个数，则右子树为$总结点个数-t-1$(1是减掉根)，乘法原理把两个乘起来，方程为

$dp[i][j]=\sum dp[t][j-1]\times dp[i-t-1][j-1]$

正常题

[SDOI2011]消耗战

题意：给定$n$个点有边权的树，割断边花费边权，求使$k$个点与$1$点不连通的最小花费。

要用虚树做，写一下方程。

设$dp[n]$为使以$n$为结点的子树内关键点都不与$n$联通的最小花费，方程为

$dp[u]=dp[u]+ \begin{cases} \min(dp[v],dist_{u,v})& \text{v不是关键点}\\ dist_{u,v}& \text{v是关键点} \end{cases}$

[ZJOI2010]排列计数

题意：求一个$1\sim n$的排列$Pi$使$ 1\leq i \leq n$时$P_i>P{i/2}$的方案数。

直接做没什么思路，可以想一下除二的关系可以是二叉树，于是换到树上来做，求$n$个节点的二叉树满足小根堆性质树的个数。

设$dp[i]$表示以$i$为根的子树内满足小根堆性质的方案数，$s[i]$为树结点数，提前把一些越界的初值设为$1$以免判断，转移时组合数算一下选给左子树的点，记得减去根节点，乘一下两颗子树的方案数就ok了，组合数要用lucas，方程

$dp[i]=C_{s[i]-1}^{s[i\times 2]}dp[i\times 2]dp[i\times 2+1]$

[SCOI2008]奖励关

题意：$m$种物品，给你n次随机在$1\sim m$间的物品，每种物品有价值并且选这种物品需要你在前$n-1$次把集合$S$内的物品种类都选过一次才可以选。

显然$m$非常小，那么求期望直接枚举就可以了，这样就好做了，然后在考虑一下如果顺推的话需要保证$S$的合法性，这个比较难处理，那么逆推显然更好写。设$dp[i][S]$表示取前$i-1$次的状态为$S$是期望的最大值，$pre[i]$为第$i$种物品的前提集合，方程枚举第i个选第k种

$dp[i][S]=dp[i][S]+ \begin{cases} \max(dp[i+1][S],dp[i+1][S|(1<<(k-1))]+val[k])& pre[i]\subseteq S \\ dp[i+1][S]& pre[i]\nsubseteq S \end{cases}$

每次$dp[i][S]$转移完之后变成$\dfrac{dp[i][S]}{n}$来求期望，答案是$dp[1][0]$.

[NOIP2014]子矩阵

首先想了一个线性dp的做法，但写完后发现完全不对，于是非常自闭，看了数据范围，直接写状压，卡了卡常就过了.

设dp[i][k][S]为到第i行选了k行，行的状态为S的最小值，转移显然.

#include <iostream>
#include <cstdio>
#include <cstring>
#define R register

using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, r, c;
int a[25][25];
int dp[17][17][1<<16];
int S[1<<16], cnt;
inline int abs(int x)
{
    return x > 0 ? x : -x;
}
inline int ck(int x)
{
    int r = 0;
    while(x) {
        if(x&1) r++;
        x>>=1;
    }
    return r;
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &r, &c);
    for(R int i = 1; i <= n; i++)
        for(R int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    for(R int s = (1<<c)-1; s <= (1<<m)-1; s++)
        if(ck(s) == c)
            S[++cnt] = s;
    memset(dp, 0x3f, sizeof(dp));
    for(R int i = 1; i <= n; i++)
        for(R int s = 1; s <= cnt; s++)
            dp[i][1][S[s]] = 0;
    for(R int i = 1; i <= n; i++)
    {
        int ed1 = min(i, r);
        for(R int l = 1; l <= ed1; l++)
        {
            if(l >= 2)
            {
                int ed2 = l-1;
                for(R int j = i-1; j >= ed2; j--)
                {
                    int tmp = 0;
                    for(R int s = 1; s <= cnt; s++)
                        if(dp[j][l-1][S[s]] != inf)
                    {
                        tmp = 0;
                        for(R int k = 1; k <= m; k++)
                            if(S[s] & (1<<(k-1)))
                                tmp += abs(a[i][k] - a[j][k]);
                        dp[i][l][S[s]] = min(dp[i][l][S[s]], dp[j][l-1][S[s]] + tmp);
                        tmp = 0;
                    }
                }
            }
            for(R int s = 1; s <= cnt; s++)
                if(dp[i][l][S[s]] != inf)
            {
                int Last = 0;
                for(R int k = 1; k <= m; k++)
                    if(S[s] & (1<<(k-1)))
                {
                    if(Last) dp[i][l][S[s]] += abs(a[i][k] - a[i][Last]);
                    Last = k;
                }
            }
        }
    }
    int ans = 0x7fffffff;
    for(R int i = 1; i <= n; i++)
        for(R int s = 1; s <= cnt; s++)
                ans = min(ans, dp[i][r][S[s]]);
    printf("%d\n", ans);
    return 0;
}

本文由落影汐雾原创，采用保留署名-非商业性使用-禁止演绎 4.0-国际许可协议
本文链接：https://x.lyxw.xyz/2019/dp/