DFS

几乎所有的DP都可以转化为搜索。当想不出正解时,DFS也是骗分的好手段。

主要的搜索手段有:

  1. DFS/BFS爆搜
  2. 双向BFS
  3. 启发式搜索(又称A*)
  4. 迭代加深搜索
  5. IDA*(迭代加深+启发式)
  6. 记忆化搜索
  7. 剪枝

重要程度:1,7,6 - 4,3 - 5,2。

下面这几道题都是去年当时不会做的,结果一年过去了,还是不会,呜呜呜

P3956 棋盘

NOIp 2017 普及

搜索裸题

显然不可以用vis[]来判断,因此会搜到重复的状态,考虑记忆化搜索。

网上的题解好像都没有正确性证明,可能觉得太显然了?可我就在这里卡了好久啊 /kk

  • 如果当前格子本来就有颜色,那么魔法一定可用
  • 如果当前格子原本没有颜色,那么只要搜到这个格子,魔法其实只有一种情况就是不可用

而且记搜的时候注意剪枝条件一定要写到上界!比如下面这段代码,f >= mem[x][y] 如果改成 f > mem[x][y],100直接变70……

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int m, n, c[N][N], mem[N][N];
int d[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
int ans = 0x3f3f3f3f;

void dfs(int x, int y, int f, int cc) {
    
    //f: 代价
    //cc != -1 不能用魔法, 此处改成的颜色
    //cc == -1 可以
    
    if(f >= mem[x][y] || f >= mem[m][m]) return;
    mem[x][y] = f;
    
    if(x == m && y == m) return;
    
    for(int i=0; i<4; ++i) {
        int xx=x+d[i][0],yy=y+d[i][1];
        if(xx<1||xx>m||yy<1||yy>m) continue;
        if(cc!=-1&&c[xx][yy]==cc||cc==-1&&c[xx][yy]==c[x][y]) {
            dfs(xx, yy, f, -1);			
        } else if(cc!=-1&&c[xx][yy]!=cc&&c[xx][yy]!=-1||cc==-1&&c[xx][yy]!=c[x][y]&&c[xx][yy]!=-1) {
            dfs(xx, yy, f+1, -1); 
        } else if(cc==-1&&c[xx][yy]==-1) {
            dfs(xx, yy, f+2, c[x][y]);
        }
    }
}
int main() {
    
    scanf("%d%d", &m, &n);
    
    memset(c, -1, sizeof c);
    memset(mem, 0x3f, sizeof mem);
    
    for(int i=1; i<=n; ++i) { 
        int x, y, cc; scanf("%d%d%d", &x, &y, &cc); 
        c[x][y] = cc;
    }
    
    dfs(1, 1, 0, -1);
    
    printf("%d\n", mem[m][m] == 0x3f3f3f3f ? -1 : mem[m][m]);
    return 0;
}

P3959 宝藏

NOIp 2017 提高

去年做的时候就连70分做法都不会。一年过去了,还是不会,呜呜呜

(下面为自己开脱)

这道题的部分分思想其实还挺重要的。

我们知道,一般的DFS就是在找出很多单条路径的过程中,获得最优答案。形式也很固定,一般形如:

void/int dfs(int u, int sum, int cnt, ...)

而这道题不然。

从样例二就可以看出,最终合法方案呈树形,而不是单条路径。初步想到生成树,但是假掉了。、

反例:

这张图从1号点开始的Prim便是错的。

如果跑Prim,从1号点开始的话,我们会先访问2,(此时花费为1),然后我们会访问3,此时花费为3 * 2,然后由于只有4号点未访问,这时3号的访问顺序为3,访问4号的代价是3 * 100 = 300,显然这种做法不是最优的,正确的答案应该是211(从1号点开始的最小花费为211)。

虽然直接跑Prim是错的,但是Prim的思想仍然重要,这一思想也在最短路等很多算法中有应用:用更新过的点去更新其他点。

我们设计一个不基于点的dfs函数,参数只需传递代价,每次迭代,先枚举访问过的点,再枚举一个未访问且未开通路径的点,进行松弛,将代价持续传递下去。计算代价需要记录点的深度,也要通过父节点传递下去。

代码不长,也不难写,说是白给70分,其实思路并不好想(虽然比正解 $O(n \times 3^n)$ 状压好写多了)。毕竟是紫题嘛,像我这种菜鸡也不打算AC,能骗多少是多少。

总的来说,这道题的关键还是在于生成树,需要认真看题,熟练运用普及算法(

Code:

#include <cstdio>
#include <cstring>
const int INF = 0x7f7f7f7f;

int min(int a, int b) { return a < b ? a : b; }

int map[20][20];
int dep[20], best, n, m, num;
bool vis[20];

void dfs(int x) {
    if(x >= best) return;
    if(num == 0) {
        best = x;
        return;
    }
    for(int i=1; i<=n; ++i) {
        if(vis[i]) {
            for(int j=1; j<=n; ++j) {
                if(!vis[j] and map[i][j] < INF) {
                    vis[j] = true; --num;
                    dep[j] = dep[i] + 1;
                    dfs(x + map[i][j] * dep[j]);
                    vis[j] = false; ++num;
                }
            }
        }
    }
}

int main() {
    memset(map, 0x7f, sizeof map);
    
    scanf("%d%d", &n, &m);
    
    for(int i=1; i<=m; ++i) {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        map[x][y] = map[y][x] = min(map[x][y], v);
    }
    
    best = INF; num = n;
    for(int i=1; i<=n; ++i) {
        vis[i] = true; --num;
        dep[i] = 0;
        dfs(0);
        vis[i] = false; ++num;
    }
    
    printf("%d\n", best);
    
    return 0;
}

常用操作

设全集为 $x$

  • for(int y = x; y; y = (y-1) & x):枚举 x 的每个子集
  • x^y:x 集合中刨去 y
  • x&y == y:y 是 x 的子集

P3052 [USACO12MAR]Cows in a Skyscraper G

树形 DP

P1352 没有上司的舞会

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;

typedef vector<int>::iterator IT;
const int N = 6e3 + 10;

int fa[N]; vector<int> g[N];
int n, r[N];
inline int fin() {
    for(int i=1; i<=n; ++i) if(!fa[i]) return i;
}

int f[N][2];// 0/1
void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for(IT it = g[u].begin(); it != g[u].end(); ++it) {
        dfs(*it);
        f[u][0] += max(f[*it][0], f[*it][1]);
        f[u][1] += f[*it][0];
    }
}
int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) scanf("%d", r+i);
    for(int i=1; i<n; ++i) { int l, k;
        scanf("%d%d", &l, &k); fa[l] = k;
        g[k].push_back(l);
    }
    int rt = fin();
    dfs(rt);
    printf("%d", max(f[rt][0], f[rt][1]));
    return 0;
}

P2014 [CTSC1997]选课

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;

const int N = 330;
vector<int> g[N];
int n, m; int dp[N][N];
void dfs(int u) {
    for(vector<int>::iterator it = g[u].begin(); it != g[u].end(); it++) {
        dfs(*it);
        for(int j=m+1; j>1; --j) {
            for(int k=0; k<j; ++k)
                dp[u][j] = max(dp[u][j], dp[*it][k] + dp[u][j-k]);
        }	
    }
}
int main() {
    
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i) { int k;
        scanf("%d%d", &k, &dp[i][1]);
        g[k].push_back(i);
    }
    dfs(0);
    printf("%d\n", dp[0][m+1]);
    return 0;
}