动态规划-二进制+状态压缩

---

动态规划：状态表示 + 状态计算

状态压缩：使用整数来表示状态 二进制数字

例题：acwing91

1.状态表示：$f[i,j]$ 所有从0到j，走过的所有点是i的所有路径，i为2进制数，0-1表示是否经过，表示状态$S$。

2.属性是求得$min$值

3.状态分割-状态计算，

从倒数第二个点的状态开始分割，[0,1…n -1],倒数第二个点为k, 0->k,k->j,k->j固定，求0->k的最小表示为$f[i-[j],k]$

即得到$Min(f[i-[j],k] + a[k,j])$

#include<bits/stdc++.h>
using namespace std;
const int N = 20, M = 1 << N;
int f[M][N], w[N][N];
int n;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0;j < n;j ++)
            cin >> w[i][j];
    
    //初始化先假设未走通道路为无穷，待更新
    memset(f,0x3f,sizeof f);
    f[1][0] = 0;
    for(int i = 0; i < 1 << n; i ++)
        for(int j = 0; j < n; j ++)
            //此时状态要满足
            if(i >> j && 1)
            {
                for(int k = 0; k < n;k ++)
                {
                    if(i - (1 << j) >> k & 1)
                    {
                        f[i][j] = min(f[i][j],f[i - (1 << j)][k] + w[k][j]);
                        //cout << f[i][j] << endl;
                    }
                }
            }
    cout << f[(1 << n) - 1][n - 1] << endl;//注意运算优先级
    return 0;
}

树形dp

例题：acwing285

建立树形结构，从根节点递归求解

分为$f[u,1]/f[u,0]$两部分求max

1.状态表示$f[u,0],$从所有以$u$为根的子树中选择，不选择$u$的集合；$f[u,1]$所有从以u为根的子树中选择，并选择$u$的集合 。

2.集合属性$Max$

3.状态转移如上图

4.前向星建立树

#include<bits/stdc++.h>
using namespace std;
const int N = 6010;
int n;
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_father[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
    f[u][1] = happy[u];
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0]; 
    }
}
int main()
{
   cin >> n;
    for(int i = 1; i <= n ; i ++) scanf("%d",&happy[i]);
    memset(h,-1,sizeof h);
    for(int i = 1; i <= n - 1;i ++)
    {
        int a, b;
        cin >> a >> b;
        has_father[a] = 1;
        add(b, a);
    }
    int root = 1;
    while(has_father[root]) root ++;
    //找到根节点并且从根节点开始
    dfs(root);
    cout << max(f[root][0],f[root][1]) << endl;
    return 0;
}

记忆化搜索

acwing901

遍历过程不可存在环，否则状态转移无法结束

和bfs思路很像

#include<bits/stdc++.h>
using namespace std;
const int N = 310;
int h[N][N], f[N][N];
int n, m;
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1};
int dp(int x, int y)
{
    int &v = f[x][y];
    //此处的v引用很关键，保留了搜索过程中的最大状态，对f[][]完成修改，不重复计算
    //如果使用dfs每个x,y开始都会重复搜索最大的路径 时间复杂度大
    if(v != -1) return v;
    v = 1;
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 1 && a <= n && b >= 1 && b <= m && h[x][y] > h[a][b])
            v = max(v, dp(a,b) + 1);
    }
    return v;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m;j ++)
            scanf("%d",&h[i][j]);
    
    memset(f, -1, sizeof f);
    int res = 0;
    for(int i = 1;i <= n;i ++)  
        for(int j = 1; j <= m; j ++)
            {
                res = max(res, dp(i, j));
                //cout << dp(i, j) << endl;
            }
    
    cout << res << endl;
    return 0;
}