初级的动态规划

发布于 2018-07-30  383 次阅读


感觉自己 dp 非常的差,于是在这里集中整理一下。

这里都是非常初级的动态规划。

定义

何为动态规划? 大概上就是一个不断探索问题性质减少那些和答案有关的值的个数。

动态规划重要的三部曲:

  • 设计状态
  • 考虑转移
  • 考虑优化

由于这里是入门级别的动态规划,将不会考虑到优化。

背包问题

常见的背包问题

那我们来看一些题目吧。

BZOJ 2287

题目描述

ftiasch 有 $ N $ 个物品, 体积分别是 $W_1, W_2, \cdots , W_N $ 。 由于她的疏忽, 第 $ i $ 个物品丢失了。 要使用剩下的 $ N - 1 $ 物品装满容积为 $ x $ 的背包,有几种方法呢?-- 这是经典的问题了。她把答案记为 $ Count(i, x) $  ,想要得到所有 $ 1 \leq i \leq N, 1 \leq x \leq M $ 的 $ Count(i, x) $  表格。

其中$ 1 \leq N \leq 2*10^3 $

$ 1 \leq M \leq 2*10^3 $

解题报告

这是一道经典的退背包问题。

我们设 $ f_i $ 表示填满容量为 $ i $ 的背包的方案数,状态转移方程显然是:

$$ f_i = f_{i-1} + f_{j-w_i}$$

然后按照题目意思,记 $ C_{i,x} $ 为不使用第 $ i $ 个物品填满容量为 $ x $ 的背包的方案数,状态转移方程显然是:

$$ C_{i,x} = \begin{cases} f_j - C_{i,x-w_j} & w_j \leq j \ f_j & w_j=j \ 1 & j=0\end{cases} $$

然后输出即可,时间复杂度 $ O(N^2) $

本质上是一个多项式除一个单项式。

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

const int MAXN = 2000 + 5;
const int ha = 10;

int a[MAXN],f[MAXN],c[MAXN][MAXN];
int N,M;

int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1;i <= N;i++)
        scanf("%d",a + i);
    f[0] = 1;
    for(int i = 1;i <= N;i++)
        for(int j = M;j >= a[i];j--)
            f[j] = (f[j] + f[j-a[i]])%ha;
    for(int i = 1;i <= N;i++){
        c[i][0] = 1;
        for(int j = 1;j <= M;j++){
            if(j >= a[i]) c[i][j] = (f[j] - c[i][j-a[i]] + ha) % ha;
            else c[i][j] = f[j];
            printf("%d",c[i][j]);
        }
        puts("");
    }   
    getchar();getchar();
    return 0;
}

BZOJ 4033

题目描述

有一棵点数为 $ N $ 的树,树边有边权。给你一个在 $ [0,N] $ 之内的正整数 $ K $ ,你要在这棵树中选择 $ K $ 个点,将其染成黑色,并将其他的 $ N-K $ 个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。

其中 $ N \leq 2000 $ .

解题报告

我们定义状态 $ f_{v,i} $ 为以 $ v $ 为根的子树中选取 $ i $ 个黑色节点对总答案贡献的最大价值。

这里的贡献如果按照题目定义,会特别难以计算,时间复杂度飙升。

所以我们自己定义边的贡献 $ val $ 为:边一侧的黑节点数*另一侧的黑节点数*边权+一侧的白节点数*另一侧的白节点数*边权 。

那么这个就变成了一个~~小清新~~背包问题。

我们可以列出转移方程为:

$$ f_{u,i} = max(f_{u,i},f_{u,i-j}+f_{v,j} + val) $$

其中枚举 $ v $ 为 $ u $ 的子节点, $ j $ 为在以 $ v $ 为根的子树中枚举选择的黑点。 $ val $ 为该条边的贡献。

$ val=j(k-j)w + (v_{size}-j)(N-K+j-size_v)w $

其中 $ w $ 为边的边权, $ v_{size} $ 为以 $ v $ 为根的子树的节点数量。

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define LL long long
//#define max(a,b) a > b ? a : b

const int MAXN = 2000 + 5;

int N,K;
LL f[MAXN][MAXN];

struct Node{
    struct Edge *firstEdge;
    int size,num;
}node[MAXN];

struct Edge{
    Node *s,*t;
    int w;
    Edge *next;
}pool[MAXN * 2],*frog = pool;

Edge *New(Node *s,Node *t,int w){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->w = w;ret->next = s->firstEdge;
    return ret;
}

void dfs(Node *v,Node *fa){
    v->size = 1;
    f[v->num][0] = f[v->num][1] = 0;
    for(Edge *e = v->firstEdge;e;e = e->next){
        if(e->t == fa) continue;
        dfs(e->t,v);
        v->size += e->t->size;
    }
    for(Edge *e = v->firstEdge;e;e = e->next){
        if(e->t == fa) continue;
        for(int i = std::min(K,v->size);i >= 0;i--){ // 当前树选择点
            for(int j = 0;j <= std::min(i,e->t->size);j++){ // 子树选择点
                if(f[v->num][i-j] != -1){ 
                    LL val = (LL)j * (K-j) * e->w + (LL)(e->t->size - j) * (N - K + j - e->t->size) * e->w;
                    f[v->num][i] = std::max(f[v->num][i],f[v->num][i-j] + f[e->t->num][j] + val);
                }
            }
        }
    }
}

inline void add(int u,int v,int w){
    node[u].firstEdge = New(&node[u],&node[v],w);
    node[v].firstEdge = New(&node[v],&node[u],w);
}

int main(){
    scanf("%d%d",&N,&K);
    memset(f,-1,sizeof(f));
    for(int i = 1;i <= N;i++) 
        node[i].num = i;
    for(int u,v,w,i = 1;i < N;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    dfs(&node[1],&node[0]);
    printf("%lld\n",f[1][K]);
    getchar();getchar();
    return 0;
}

总结

对于这种问题,找出题目中隐藏的容量和价值,巧妙转移问题,有时价值太难算可以自己选取一个正确好算的价值。

数位 dp

BZOJ1026

题目描述

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为 $ 2 $ 的正整数被称为windy数。 windy想知道,在 $ A $ 和 $ B $ 之间,包括 $ A $ 和 $ B $ ,总共有多少个windy数?

其中 $ 1 \leq A \leq B \leq 10^{18} $

解题报告

直接数位 dp。

设 $ f_{i,j} $ 表示考虑前 $ i $ 位,上一位是 $ i-1 $ 的方案数。

转移方程是
$$ f_{i,j} = f_{i,j} + f_{i-1,k}(j-k \geq 2) $$

直接计数统计即可。

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define LL long long

const int BASE = 12 + 5;

LL f[BASE][BASE];
LL a,b;
int dight[BASE];
int len;

void init(){
    memset(f,0,sizeof(f));
    for(int i = 0;i <= 9;i++){
        f[1][i] = 1;
    }
    for(int i = 2;i <= 10;i++){
        for(int j = 0;j <= 9;j++){
            for(int k = 0;k <= 9;k++){
                if(std::abs(j - k) >= 2)
                    f[i][j] += f[i-1][k];
            }
        }
    }
}

LL solve(LL x){
    LL ret = 0;
    if(!x) return 0;
    memset(dight,0,sizeof(dight));
    len = 0;
    while(x){
        dight[++len] = x % 10;
        x /= 10;
    }
    for(int i = 1;i <= dight[len] - 1;i++)
        ret += f[len][i];
    for(int i = len - 1;i > 0;i--)
        for(int j = 1;j <= 9;j++)
            ret += f[i][j];
    for(int i = len-1;i > 0;i--){
        for(int j = 0;j <= dight[i]-1;j++)
            if(std::abs(dight[i + 1]-j) >= 2) ret += f[i][j];
        if(std::abs(dight[i + 1] - dight[i]) < 2) break;
    }
    return ret;
}
    
int main(){
    scanf("%lld%lld",&a,&b);
    init();
    printf("%lld",solve(b + 1) - solve(a));
    getchar();getchar();
    return 0;
}

BZOJ1799

题目描述

给出 $ a,b $ ,求出 $ [a,b] $ 中各位数字之和能整除原数的数的个数.

其中 $ 1 \leq a \leq b \leq 10^{18} $

解题报告

我们设状态 $ f[i][j][k][0/1] $ 表示考虑前 $ i $ 位,数字和为 $ j $ ,数字和 $ mod\ m $ 为 $ k $ ,是否卡上界的情况下的方案数。

转移方程在代码里,就不写了。

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long

const int BASE = 20 + 5;
const int MAX_SUM = 200 + 5;

LL f[BASE][MAX_SUM][MAX_SUM][2];
int sum = 9 * 18 + 1;
LL a,b;
int dight[BASE];

LL pre(LL x,int ha){
    if(!x) return 0;
    memset(f,0,sizeof(f));
    int cnt = 0;
    while(x){
        dight[++cnt] = x % 10;
        x /= 10;
    }
    f[cnt + 1][0][0][0] = 1;
    for(int i = cnt + 1;i > 1;i--){
        for(int j = 0;j <= ha;j++){
            for(int k = 0;k < ha;k++){
                if(!f[i][j][k][0] && !f[i][j][k][1]) continue;
                for(int p = 0;p <= 9;p++){
                    if(p < dight[i-1] && (j + p <= ha)) 
                        f[i-1][j+p][(10 * k + p)%ha][1] += f[i][j][k][0];
                    else if(p == dight[i-1] && (j + p <= ha))
                        f[i-1][j+p][(10 * k + p)%ha][0] += f[i][j][k][0];
                    if(f[i][j][k][1] && (j + p <= ha)) 
                        f[i-1][j+p][(10 * k + p)%ha][1] += f[i][j][k][1]; 
                }
            }
        }
    }
    return f[1][ha][0][0] + f[1][ha][0][1];
}

int main(){
    scanf("%lld%lld",&a,&b);
    LL ans = 0;
    for(int i = 1;i < sum;i++)
        ans += pre(b,i) - pre(a-1,i);
    printf("%lld\n",ans);
    getchar();getchar();
    return 0;
}

总结

对于数位 dp,主要是注意位与位之间的转换的公式推导和情况特判,细心。统计答案时对上下界和其他特殊情况的特判。这种问题较为简单,有规律可循。

状压 dp

BZOJ2560

题目描述

铭铭有 $ n $ 个十分漂亮的珠子和若干根颜色不同的绳子。现在铭铭想用绳子把所有的珠子连接成一个整体。

现在已知所有珠子互不相同,用整数 $ 1 $ 到 $ n $ 编号。对于第 $ i $ 个珠子和第 $ j $ 个珠子,可以选择不用绳子连接,或者在 $ c_{i,j} $ 根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点,把绳子看作边,将所有珠子连成一个整体即为所有点构成一个连通图。特别地,珠子不能和自己连接。

铭铭希望知道总共有多少种不同的方案将所有珠子连成一个整体。由于答案可能很大,因此只需输出答案对 $ 1000000007 $ 取模的结果。

其中 $ N \leq 15 $

解题报告

我们设状态 $ f_s $ 表示将状态 $ S $ 连通的方案。由于不容易直接算,我们考虑容斥原理。

设 $ g_s $ 表示所有子图的方案。

显然 $ g_s $ 可求。

对于 $ f_s $ 的计算可以由

$$ f_s = g_s - \sum_tf_t*g_{s-t} $$

计算得来。

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define LL long long
#define ULL unsigned long long
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 20 + 5;
const int MAXS = 100000 + 5;
const int ha = 1000000007;

LL N;
LL map[MAXN][MAXN],f[MAXS],g[MAXS];

void pre(LL S){
    g[S] = 1;
    for(LL i = 1;i <= N;i++){
        if((1 << (i-1))&S)
            for(LL j = i + 1;j <= N;j++)
                if((1 << (j-1))&S)
                    g[S] = (g[S] * (map[i][j] + 1)) % ha;
    }
}

int main(int argc,char *argv[]){
    scanf("%lld",&N);
    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= N;j++)
            scanf("%lld",&map[i][j]);
    for(LL i = 0;i < (1 << N);i++) pre(i);
    for(LL S = 0;S < (1 << N);S++){
        f[S] = g[S];
        LL i = S ^ (S&-S);
        for(LL j = i;j;j=(j-1)&i) 
            f[S] = (f[S]-g[j]*f[S^j]%ha + ha)%ha;
    }
    printf("%lld\n",f[(1<

To Be Continue...


一个OIer。