动态规划（DP）

// 以下题目来自牛客网

删括号

f[i][j][k] 表示序列s的前i个匹配序列t的前j个，序列s删除部分左括号与右括号数量差为k的情况是否可行

答案为 f[sl][tl][0]

状态转移：

当 f[i][j][k] 可行时

s[i+1]==t[j+1] 且 k==0 则 f[i+1][j+1][k] = 1
s[i+1]=='(' 则s串删去当前括号可匹配，即 f[i+1][j][k+1] = 1
s[i+1]==')' 则 k>0 时s串多删去一个左括号匹配，即 f[i+1][j][k-1] = 1

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

bool f[][][];  //s前i个删去括号能否成为t前j个，左右括号差为k

char s[], t[];

int main() {

    scanf("%s", s+);

    scanf("%s", t+);

    int sl = strlen(s+), tl = strlen(t+);

    f[][][] = ;

    for(int i=;i<sl;i++) {

        for(int j=;j<tl;j++) {

            for(int k=;k<sl;k++) if(f[i][j][k]) {

                if(k== && s[i+]==t[j+]) f[i+][j+][k] = ;

                if(s[i+]=='(') f[i+][j][k+] = ;

                else if(k) f[i+][j][k-] = ;

            }

        }

    }

    printf("%s\n", f[sl][tl][]?"Possible":"Impossible");

    return ;

}

回文子序列计数

错误思路：x[i] = 左右26个小写字母选取0~min(l[i][j], r[i][j]) （0<=j<26)的组合数之积。

正确求法：见代码。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int mod = 1e9+;

typedef long long ll;

ll x[], dp[];   // dp[i]位回文子序列个数

// dp[i+1]

char s[];

int main()

{

    scanf("%s", s);

    int n = strlen(s);

    for(int i=;i<n;i++) x[i] = ;

    for(int i=;i<n;i++) {

        ll sum = , tmp;

        for(int j=n-;j>i;j--) {

            tmp = dp[j];

            if(s[j]==s[i-]) {

                dp[j] = (dp[j] + sum + ) % mod;

            }

            sum = (sum + tmp) % mod;

            x[i] = (x[i] + dp[j]) % mod;

        }

    }

    ll ans = ;

    for(int i=;i<n;i++) {

        ans = ans^((i+) * x[i]) % mod;

    }

    printf("%lld\n", ans);

    return ;

}

牛牛的计算机内存

状压dp

直接 dp[22][1<<20] 会MLE，只能用滚动数组记录状态。

int dp[1<<20]; // dp[S]: 前i条指令状态为S的最小代价
int state[1<<20]; // state[i]:j 指令状态i执行完后的内存状态为j

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int dp[<<];    // dp[S]: 前i条指令，访问完状态为S的最小代价

int state[<<]; // state[i]:S   前i条指令执行完状态为S

int a[];

int main() {

    memset(dp, INF, sizeof(dp));

    dp[] = ;

    int n, m;

    char ins[];

    scanf("%d %d", &n, &m);

    for(int i=;i<n;i++) {

        scanf("%s", ins);

        int k = ;

        for(int j=;j<m;j++) {

            a[i] = a[i]* + (ins[j]-'');

            if(ins[j]=='') ++k;

        }

        state[<<i] = a[i];

        dp[<<i] = k*k;

    }

    for(int S=;S<(<<n);S++) {

        if(dp[S]==INF) continue;

        for(int i=;i<n;i++) {

            if((S>>i)&) continue;

            int nexS = S|(<<i), k = ;

            for(int j=;j<m;j++) {

                if((a[i]>>j)& && ((state[S]>>j)&)==) {

                    ++k;

                }

            }

            if(dp[nexS]>dp[S]+k*k) {

                dp[nexS] = dp[S] + k*k;

                state[nexS] = state[S]|a[i];

            }

        }

    }

    printf("%d\n", dp[(<<n)-]);

    return ;

}

棋盘的必胜策略

可以用 f[i][j][step] 记录到 mp[i][j] 用了step步的胜负状态，dfs即可。

如果下一步有必败态，当前则为必胜态
否则当前为必败态
mp[i][j]终点为必败态

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int dx[] = {, , , -};

const int dy[] = {, -, , };

int r, c, k;

char mp[][];

int f[][][];

bool check(int x, int y) {

    if(x<||y<||x>=r||y>=c)

        return false;

    if(mp[x][y]=='#')

        return false;

    return true;

}

int dfs(int x, int y, int k) {

    if(f[x][y][k]!=-)

        return f[x][y][k];

    if(mp[x][y]=='E')    // 走到终点，无法移动，必败

        return f[x][y][k] = ;

    if(k==)

        return ;        // 走不了，必败

    for(int i=;i<;i++) {

        int nx = x + dx[i];

        int ny = y + dy[i];

        if(check(nx, ny) && dfs(nx, ny, k-)==)

            return f[x][y][k] = ;

    }

    return f[x][y][k] = ;

}

int main() {

    cin>>r>>c>>k;

    for(int i=; i<r; i++)

        scanf("%s",mp[i]);

    memset(f, -, sizeof(f));

    int sx, sy;

    for(int i=;i<r;i++) {

        for(int j=;j<c;j++) {

            if(mp[i][j] == 'T') {

                sx = i;

                sy = j;

            }

        }

    }

    printf("%s\n", dfs(sx, sy, k)?"niuniu":"niumei");

    return ;

}

看起来像博弈论，其实分析一下最多走两步就能确定胜负，不用搜索状态也能解决。

分析见代码。

#include<iostream>

#include<cstdio>

using namespace std;

const int dx[] = {, , , -};

const int dy[] = {, -, , };

int r, c, k;

char mp[][];

bool check(int x, int y) {

    if(x<||y<||x>=r||y>=c)

        return false;

    if(mp[x][y]=='#')

        return false;

    return true;

}

bool win(int x, int y) {

    for(int i=;i<;i++) {

        int nx = x + dx[i];

        int ny = y + dy[i];

        if(check(nx, ny) && mp[nx][ny]=='E')

            return true;

    }

    return false;

}

int main() {

    cin>>r>>c>>k;

    for(int i=; i<r; i++)

        scanf("%s",mp[i]);

    int sx, sy;

    for(int i=;i<r;i++) {

        for(int j=;j<c;j++) {

            if(mp[i][j] == 'T') {

                sx = i;

                sy = j;

            }

        }

    }

    bool f = false;  // 第一步能否走

    for(int i=;i<;i++) {

        int nx = sx + dx[i];

        int ny = sy + dy[i];

        if(check(nx, ny)) {

            f = true;

            if(mp[nx][ny]=='E')

                return  * printf("niuniu\n");

        }

    }

    if(!f) { // 动不了

        return  * printf("niumei\n");

    }

    if(k==) { // 只走一步

        return  * printf("niuniu\n");

    }

    if(k%==) { // 偶数步，往返走，走后必胜

        return  * printf("niumei\n");

    }

    // 奇数步，第二步无法胜，第三步开始往返走，先走必胜

    for(int i=;i<;i++) {

        int nx = sx + dx[i];

        int ny = sy + dy[i];

        if(check(nx, ny) && mp[nx][ny]=='.' && !win(nx, ny)) {

            return  * printf("niuniu\n");

        }

    }

    puts("niumei");

    return ;

}

牛牛与数组

状态转移很好写，记录一下前缀和，减去dp[i-1][j] j的整数倍的部分即为dp[i][j]

#include<iostream>

#include<cstdio>

using namespace std;

const int mod = 1e9+;

int dp[][];

int main() {

    int n, k;

    scanf("%d %d", &n, &k);

    for(int i=;i<=k;i++) dp[][i] = ;

    for(int i=;i<=n;i++) {

        int sum = ;

        for(int j=;j<=k;j++)

            sum = (sum + dp[i-][j]) % mod;

        for(int j=;j<=k;j++) {

            int sum1 = ;

            for(int l=*j;l<=k;l+=j) {

                sum1 = (sum1 + dp[i-][l])% mod;

            }

            dp[i][j] = ((sum - sum1)%mod+mod)%mod;

        }

    }

    printf("%d\n", dp[n][k]);

    return ;

}

牛牛去买球

n个盒子，每个盒子有a[i]个红球，b[i]个篮球，但a[i],b[i]有正负1的偏差，总和不变。买每个盒子的费用为c[i]，求买k个相同的球的最小花费。

三种情况

买k个红球，每个盒子都当做a[i]-1个红球
买k个蓝球，每个盒子都当做b[i]-1个蓝球
买2k-1个球，至少保证有k个相同颜色的球

用滚动数组上限为最多的球数，而不是k。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int dp[];

int a[], b[], c[];

int main() {

    int n, k; cin>>n>>k;

    for(int i=;i<=n;i++)

        scanf("%d", &a[i]);

    for(int i=;i<=n;i++)

        scanf("%d", &b[i]);

    for(int i=;i<=n;i++)

        scanf("%d", &c[i]);

    int ans = 0x3f3f3f3f, up = ;

    memset(dp, 0x3f, sizeof(dp));

    dp[] = ;

    for(int i=;i<=n;i++) {

        int v = a[i] - ;

        for(int j=up;j>=v;j--) {

            dp[j] = min(dp[j], dp[j-v]+c[i]);

        }

    }

    for(int i=k;i<=*k;i++) ans = min(ans, dp[i]);

    memset(dp, 0x3f, sizeof(dp));

    dp[] = ;

    for(int i=;i<=n;i++) {

        int v = b[i] - ;

        for(int j=up;j>=v;j--) {

            dp[j] = min(dp[j], dp[j-v]+c[i]);

        }

    }

    for(int i=k;i<=*k;i++) ans = min(ans, dp[i]);

    memset(dp, 0x3f, sizeof(dp));

    dp[] = ;

    for(int i=;i<=n;i++) {

        int v = a[i]+b[i];

        for(int j=up;j>=v;j--) {

            dp[j] = min(dp[j], dp[j-v]+c[i]);

        }

    }

    for(int i=*k-;i<=up;i++) ans = min(ans, dp[i]);

    if(ans==0x3f3f3f3f) ans = -;

    printf("%d\n", ans);

    return ;

}

小明打联盟

有3个小技能一个大招，大招的伤害值随时间线性变化。给定T时间，以及各个技能的释放时间和伤害值，问最大的伤害值是多少。

不考虑大招的话，就是多重背包问题。

把一个大招看成两个L, R时刻释放的大招d, e，中间时刻释放只会用一次。（假设用两次m时刻的大招可以转化为大招e + (2m-l)时刻的大招，还是相当于用一次）

然后再枚举L，R区间的最大伤害值即可。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int t;

int v[];

int w[];

long long dp[];

int main() {

    while(scanf("%d", &t)!=EOF) {

        for(int i=;i<;i++) {

            scanf("%d %d", &v[i], &w[i]);

        }

        int L, R, temp, A;

        scanf("%d %d %d %d", &L, &R, &temp, &A);

        v[] = L; w[] = temp;

        v[] = R; w[] = temp + A*(R-L);

        memset(dp, , sizeof(dp));

        for(int i=;i<;i++) {

            for(int j=v[i];j<=t;j++) { // 多重背包

                dp[j] = max(dp[j], dp[j-v[i]]+w[i]);

            }

        }

        for(int j=L;j<=R;j++) {

            dp[t] = max(dp[t], dp[t-j]+temp+1LL*A*(j-L));

        }

        printf("%lld\n", dp[t]);

    }

    return ;

}

树形dp

// 以下题目来自洛谷

P1352 没有上司的舞会

状态转移方程很简单，1A

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

int n, fa[];

int w[];

vector<int> G[];

int dp[][];

// dp[u][0] u没有参加

// dp[u][1] u参加

void dfs(int u, int fa) {

    dp[u][] = w[u];

    for(int i=;i<G[u].size();i++) {

        int v = G[u][i];

        if(v==fa) continue;

        dfs(v, u);

        dp[u][] += dp[v][];

        dp[u][] += max(dp[v][], dp[v][]);

    }

}

int main() {

    scanf("%d", &n);

    for(int i=;i<=n;i++)

        scanf("%d", &w[i]);

    int u, v;

    for(int i=;i<n;i++) {

        scanf("%d %d", &u, &v);

        G[u].push_back(v);

        G[v].push_back(u);

        fa[u] = v;

    }

    int rt = -;

    for(int i=;i<=n;i++)

        if(!fa[i]) {

            rt = i;

            break;

        }

    dfs(rt, -);

    printf("%d\n", max(dp[rt][], dp[rt][]));

    return ;

}

P2016 战略游戏

选出一棵树上最少的节点，能覆盖所有边。

这题结构跟上面类似，每一点放/不放两个状态。

查看题解有大佬指出这是最小点覆盖问题，使用匈牙利算法，对于无向图答案为 ans / 2 。

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int maxn = ;

vector<int> G[maxn];

int n;

int f[maxn][];

void dfs(int u, int fa) {

    f[u][] = ;

    for(int i=;i<G[u].size();i++) {

        int v = G[u][i];

        if(v==fa) continue;

        dfs(v, u);

        f[u][] += f[v][];

        f[u][] += min(f[v][], f[v][]);

    }

}

int main() {

    scanf("%d", &n);

    for(int i=;i<n;i++) {

        int u, v, k;

        scanf("%d %d", &u, &k);

        while(k--) {

            scanf("%d", &v);

            G[u].push_back(v);

            G[v].push_back(u);

        }

    }

    dfs(, -);

    printf("%d\n", min(f[][], f[][]));

    return ;

}

P2015 二叉苹果树

保留K条边苹果树上的最大苹果数量。

注意子树边的数量写法：dfs儿子后 sz[u] += sz[v] + 1;

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int maxn = ;

int n, K;

struct Edge {

    int to, w;

    Edge(int v, int ww):to(v), w(ww){}

};

vector<Edge> G[maxn];

int sz[maxn];

int dp[maxn][maxn];

// dp[u][i] ： 以u为根的子树保留i条边的最多苹果数量

void dfs(int u, int fa) {

    for(int i=;i<G[u].size();i++) {

        int v = G[u][i].to;

        if(v==fa) continue;

        dfs(v, u);

        sz[u] += sz[v] + ;    // 边的数量

        for(int j=min(sz[u], K);j>=;j--) { // 01背包，逆序

            for(int k=;k<=min(sz[v], j-);k++) {

                dp[u][j] = max(dp[u][j], dp[u][j-k-] + dp[v][k] + G[u][i].w);

            }

        }

    }

}

int main() {

    scanf("%d %d", &n, &K);

    int u, v, w;

    for(int i=;i<n;i++) {

        scanf("%d %d %d", &u, &v, &w);

        G[u].push_back(Edge(v, w));

        G[v].push_back(Edge(u, w));

    }

    dfs(, -);

    printf("%d\n", dp[][K]);

    return ;

}

P2014 选课

课程之间有依赖关系，求选M门课程的最大学分。

将没有直接先修课的课程连在根为 0 的树上，从节点 0 dfs 即可。

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int maxn = ;

int n, K;

vector<int> G[maxn];

int sz[maxn], w[maxn];

int dp[maxn][maxn];

// dp[u][i] ： 以u为根的子树选i门课的最大学分

void dfs(int u) {

    sz[u] = ;

    for(int i=;i<G[u].size();i++) {

        int v = G[u][i];

        dfs(v);

        sz[u] += sz[v];

        for(int j=min(sz[u], K);j>=;j--) {

            for(int k=;k<=min(j-, sz[v]);k++) {

                dp[u][j] = max(dp[u][j], dp[u][j-k-] + dp[v][k]);

            }

        }

    }

}

int main() {

    scanf("%d %d", &n, &K);

    int fa;

    for(int i=;i<=n;i++) {

        scanf("%d %d", &fa, &w[i]);

        G[fa].push_back(i);

    }

    for(int i=;i<=n;i++) dp[i][] = w[i];

    dfs();

    printf("%d\n", dp[][K]);

    return ;

}

P1270 “访问”美术馆

读入采用dfs形式给出美术馆的通过走廊的时间和藏画数量，问T时间内能盗窃多少幅画。

坑点：时间有效时间为 T - 1

记搜 / 树形dp 。由于要返回根节点，时间可以直接乘以 2 读入。

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int maxn = ;

int T, tot;

struct node {

    int cost, val;

}tree[maxn*];

int dp[maxn*][];

void dfs(int u, int t) {

    if(dp[u][t] || t==)  return; // 0为0直接返回

    if(tree[u].val) { // 根节点

        dp[u][t] = min(tree[u].val, (t-tree[u].cost)/);

        return;

    }

    for(int i=;i<=t-tree[u].cost;i++) {

        dfs(u*, i);

        dfs(u*+, t-i-tree[u].cost);  // 右边剩下时间=  t - i - 2倍走廊时间

        dp[u][t] = max(dp[u][t], dp[u*][i]+dp[u*+][t-i-tree[u].cost]);

    }

}

void build(int rt) {

    scanf("%d %d", &tree[rt].cost, &tree[rt].val);

    tree[rt].cost *= ;

    if(!tree[rt].val) {

        build(rt*);

        build(rt*+);

    }

}

int main() {

    scanf("%d", &T);

    build();

    dfs(, T-);

    printf("%d\n", dp[][T-]);

    return ;

}

数位DP

// 以下来自洛谷

P2657 [SCOI2009]windy数

求A，B区间内满足相邻两位数字之差大于等于2的整数个数。

注意是在 !lim && !zero 条件下记忆化，没加这个条件调了半天。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll dp[][]; // dp[i][j]:长度为i中最高位是j的windy数的个数

int bit[];

ll dfs(int pos, int lim, int last, int zero) {

    if(pos<) return ;

    if(!lim && !zero && dp[pos][last]!=-) return dp[pos][last];

    int res = ;

    int up = lim?bit[pos]:;

    for(int i=;i<=up;i++) {

        if(abs(i-last)<) continue;

        res += dfs(pos-, lim&&(i==up), zero&&(i==)?:i, zero&&(i==));

    }

    if(!lim && !zero) dp[pos][last] = res;

    return res;

}

ll cal(ll x) {

    int cnt = ;

    while(x) {

        bit[cnt++] = x%;

        x /= ;

    }

    memset(dp, -, sizeof(dp));

    return dfs(cnt-, , , );

}

int main() {

    ll A, B;

    while(cin>>A>>B)

    printf("%lld\n", cal(B)-cal(--A));

    return ;

}

洛谷题解翻到别人的代码处理：

巴特西

dp练习集