算法模板(4):动态规划(2)

这篇具有很好参考价值的文章主要介绍了算法模板(4):动态规划(2)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

8.树形DP

没有上司的舞会

树上最大独立集问题

Ural 大学有 N N N 名职员,编号为 1 ∼ N 1 \sim N 1N。他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数,用整数 H i H_i Hi 给出,其中 1 ≤ i ≤ N 1 \le i \le N 1iN。现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 6010;
int h[maxn], e[maxn], ne[maxn], idx;
bool has_father[maxn];
int f[maxn][2], N, happy[maxn];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u) {
//f[u][0]是不选u, f[u][1]是选u。
	f[u][1] = happy[u];
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		dfs(v);
		f[u][0] += max(f[v][0], f[v][1]);
		f[u][1] += f[v][0];
	}
}
int main() {
	memset(h, -1, sizeof h);
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", &happy[i]);
	for (int i = 1; i < N; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(b, a);
		has_father[a] = true;
	}
	int root;
	for (root = 1; root <= N && has_father[root]; root++);
	dfs(root);
	printf("%d\n", max(f[root][0], f[root][1]));
	return 0;
}

1072. 树的最长路径

  • 题意:给定一棵树,树中包含 n n n 个结点(编号 1 1 1~ n n n)和 n − 1 n-1 n1 条无向边,每条边都有一个权值。现在请你找到树中的一条最长路径。换句话说,要找到一条路径,使得使得路径两端的点的距离最远。注意:路径中可以只包含一个点。

法一:

(1)任取一点 a a a 作为起点,找到距离该点最远的点 u u u. (2)再找到距离 u u u 最远的一点 v v v

u u u v v v 之间的路径是树的直径. 证明的话,只需证 u u u 的是直径的一个端点;用反证法,假设 c d cd cd 是真的直径,那么可以分为 c d cd cd u a ua ua 的直径是否有公共点. 具体可以看视频.

#include<bits/stdc++.h>
using namespace std;
const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;

int h[N], e[M], ne[M], w[M], idx;
int n, d[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs(int u, int fa)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if(v == fa) continue;
        d[v] = d[u] + w[i];
        dfs(v, u);
    }
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    dfs(1, -1);

    int u = 0, res = -INF;
    for(int i = 1; i <= n; i++)
    {
        if(d[i] > res) res = d[i], u = i;
    }

    d[u] = 0;
    dfs(u, -1);
    res = -INF;
    for(int i = 1; i <= n; i++)
    {
        res = max(res, d[i]);
    }
    printf("%d\n", res);
    return 0;
}

法二:

记录一个子树高度的最大值和次大值即可

int ans;
int dfs(int u, int fa)
{
    int height = 0, max1 = 0, max2 = 0;
    for(int i = h[u]; i != -1; i = ne[i]){
        int v = e[i];
        if(v == fa) continue;
        int nh = dfs(v, u);
        height = max(height, nh + w[i]);
        if(nh + w[i] > max1){
            max2 = max1;
            max1 = nh + w[i];
        }
        else if(nh + w[i] > max2){
            max2 = nh + w[i];
        }
    }
    int res = 0;
    if(max1) res += max1;
    if(max2) res += max2;
    ans = max(ans, res);
    return height;
}

1073. 树的中心

  • 题意:给定一棵树,树中包含 n n n 个结点(编号 1 ∼ n 1\sim n 1n )和 n − 1 n−1 n1 条无向边,每条边都有一个权值。请你在树中找到一个点,使得该点到树中其他结点的最远距离最近。
  • 一个点距离其他所有节点的最远距离,是一个点向下走和向上走的最远距离取一个最大值. 对于结点 v v v,其父结点是 u u u,向下走容易求;向上走分为两种,一种是 u u u 向上走的最大值加上 w ( u , v ) w(u,v) w(u,v),一种是 u u u 不经过点 v v v 的路径向下走的最大值加上 w ( u , v ) w(u,v) w(u,v). 后者可以求一个向下走的最大值和次大值来获得.
#include<bits/stdc++.h>
using namespace std;
const int N = 10010, M = N * 2;

int n;
int h[N], e[M], ne[M], w[M], idx;

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int d1[N], d2[N], son1[N], son2[N];
int up[N];

int dfs1(int u, int fa)
{
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if(v == fa) continue;
        int d = dfs1(v, u) + w[i];
        if(d >= d1[u]) 
        {
            d2[u] = d1[u], d1[u] = d;
            son2[u] = son1[u], son1[u] = v;
        }
        else if(d > d2[u])
        {
            d2[u] = d, son2[u] = v;
        }
    }
    return d1[u];
}

void dfs2(int u, int fa)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if(v == fa) continue;
        //直接从当前层推到下一层.
        int dist = w[i] + (son1[u] == v ? d2[u] : d1[u]);
        up[v] = max(dist, w[i] + up[u]);
        dfs2(v, u);
    }
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    dfs1(1, -1);
    dfs2(1, -1);
    int res = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
    {
        res = min(res, max(up[i], d1[i]));
    }
    printf("%d\n", res);
    return 0;
}

9.数位统计DP

  • 技巧一: [ x , y ] = f ( y ) − f ( x − 1 ) [x, y] = f(y) - f(x - 1) [x,y]=f(y)f(x1)
  • 技巧二:用的角度考虑
  • 其实,我感觉,数位 d p dp dp 就是一个搜索的过程,从最高位是 0 0 0 ~ a n − 1 a_{n-1} an1 开始,最开始填 000...000 000...000 000...000,然后到 099...999 , 199...999 099...999, 199...999 099...999,199...999,再到 ( a n − 1 − 1 ) 99...999 (a_{n-1}-1)99...999 (an11)99...999;然后最高位填 a n − 1 a_{n-1} an1,开始填第二位。这样子,确实可以搜索完全部的数字。

杨雅儒告诉我们, f [ i , j , 0 / 1 ] f[i,j,0/1] f[i,j,0/1] 表示状态,最后一个 0 / 1 0/1 0/1 表示是否顶到上界.

度的数量

  • 题意:求给定区间 [ X , Y ] [X,Y] [X,Y] 中满足下列条件的整数个数:这个数恰好等于 K K K 个互不相等的 B B B 的整数次幂之和。

  • 计算 f ( N ) f(N) f(N)。把 N N N 写成 B B B 进制 a n − 1 a n − 2 . . . a 0 ‾ \overline{a_{n-1}a_{n-2}...a_0} an1an2...a0。那么,第一位要么填 a n − 1 a_{n-1} an1,要么填 0 0 0 ~ a n − 1 − 1 a_{n-1}-1 an11.

  • 转化为这道题。因为每一位只能填 1 1 1 0 0 0.

    • 当第 x x x 位为 0 0 0 时,只能进到右边那个分支。
    • x x x 1 1 1 时,进到左边那个分支时,第 a n − 1 a_{n-1} an1 位只能填 0 0 0,那么是 C n − 1 k C_{n-1}^{k} Cn1k 种填法,其实也就是 C i K − l a s t C_{i}^{K-last} CiKlast.
    • x > 1 x > 1 x>1 时,那么左边那个分支的第一位可以填 0 0 0 1 1 1,但是右边那个分支就没有了。

算法模板(4):动态规划(2)

#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 35;
ll C[maxn][maxn];   //组合数
int K, B;
ll dp(int n) {
	if (n == 0) return 0;
	
	vector<int> nums;
	while (n) nums.push_back(n % B), n /= B;   
	ll res = 0;      //保存答案。
	int last = 0;    //保存前缀信息。这里是保存用掉了多少个1

	for (int i = nums.size() - 1; i >= 0; i--) {
		int x = nums[i];
		if (x) {
			res += C[i][K - last];  //C(n-1, K)
			if (x > 1) {
				if (K - last - 1 >= 0) res += C[i][K - last - 1];
				break;
			}
			else {
				last++;
				if (last > K) break;
			}
		}
		if (i == 0 && last == K) res++;  
		//这个求的是方案数。跑到最右边一位时,如果此时一个1也不允许填了,那么此处填0就是这1种方案。
	}

	return res;
}
int main() {
	for (int i = 0; i < maxn; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0) C[i][j] = 1;
			else C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
		}
	}
	int L, R;
	cin >> L >> R >> K >> B;
	cout << dp(R) - dp(L - 1) << endl;
}

深搜代码

#include<bits/stdc++.h>
using namespace std;
const int N = 35;
int f[N][N][2], a[N];
int k, b, X, Y;

int dp(int pos, int k, int lim)
{
    if(pos == -1)
    {
        return k == 0;
    }
    int& v= f[pos][k][lim];
    if(v != -1) return v;
    int up = lim ? min(1, a[pos]) : 1;
    int ans = 0;
    for(int i = 0; i <= up; i++)
    {
        if(k > 0) ans += dp(pos - 1, i == 0 ? k : k - 1, i == a[pos] && lim);
        if(!k && !i) ans += dp(pos - 1, 0, i == up && lim);
    }
    return f[pos][k][lim] = ans;
}

int solve(int x)
{
    int sz = 0;
    while(x)
    {
        a[sz++] = x % b;
        x /= b;
    }
    memset(f, -1, sizeof f);
    return dp(sz - 1, k, 1);
}

int main()
{
    scanf("%d%d%d%d", &X, &Y, &k, &b);
    printf("%d\n", solve(Y) - solve(X - 1));
}

数字游戏

  • 题意:某人命名了一种不降数,这种数字必须满足从左到右各位数字呈非下降关系,如 123,446。现在大家决定玩一个游戏,指定一个整数闭区间 [ a , b ] [a,b] [a,b],问这个区间内有多少个不降数。

算法模板(4):动态规划(2)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 15;
int f[maxn][maxn];  //f[i][j] 表示最高位填 j, 且总共有 i 位的数的个数

int dp(int n) {
	if (n == 0) return 1;
	int res = 0, last = 0;
	vector<int> nums;
	while (n) nums.push_back(n % 10), n /= 10;
	for (int i = nums.size() - 1; i >= 0; i--) {
		int x = nums[i];
		for (int j = last; j < x; j++) {
			res += f[i + 1][j];
		}
		if (last > x) break;
		last = x;
        //程序能走到这里,说明a0也是合法情况,即N这个数字就是不降数
		if (i == 0) res++;
	}
	return res;
}
int main() {
	for (int j = 0; j <= 9; j++) f[1][j] = 1;
	for (int i = 2; i < 15; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = j; k <= 9; k++) {
				f[i][j] += f[i - 1][k];
			}
		}
	}
	int a, b;
	while (cin >> a >> b) {
		cout << dp(b) - dp(a - 1) << endl;
	}
	return 0;
}

深搜方法(注意,这道题前导零是合法的。举例来说,表示 [ 1 , R ] , R > 10 [1,R], R > 10 [1,R],R>10 中的数字,如果想表示出1,前面就得有前导零)

#include<bits/stdc++.h>
using namespace std;
const int N = 35;
int f[N][N], A, B;
int a[N];
//搜索到 pos 个位置,上一位是 k,的方案数.
int dp(int pos, int k, int lim)
{
    if(pos == -1) return 1;
    if(!lim && f[pos][k] != -1)
    {
        return f[pos][k];
    }
    int up = lim ? a[pos] : 9;
    int ans = 0;
    for(int i = k; i <= up; i++)
    {
        ans += dp(pos - 1, i, i == up && lim);
    }
    if(!lim) f[pos][k] = ans;
    return ans;
}

int solve(int x)
{
    //if(!x) return 1;
    int sz = 0;
    while(x)
    {
        a[sz++] = x % 10;
        x /= 10;
    }
    memset(f, -1, sizeof f);
    return dp(sz - 1, 0, 1);
}
int main()
{
    while(cin >> A >> B)
    {
        //printf("%d\n%d\n", solve(B), solve(A - 1));
        printf("%d\n", solve(B) - solve(A - 1));
    }
    return 0;
}

10. 单调队列优化DP

135. 最大子序和

  • 输入一个长度为 n n n 的整数序列,从中找出一段长度不超过 m m m 的连续子序列,使得子序列中所有数的和最大。连续子序列长度至少为 1 1 1 .
  • 打一个前缀和,让 s [ i ] − s [ i − j ] , 1 ≤ j ≤ m s[i] - s[i-j],1 \le j \le m s[i]s[ij],1jm 最大. 就是在 i − m ∼ i − 1 i - m \sim i - 1 imi1 中找最小值.
#include<bits/stdc++.h>
using namespace std;
const int N = 300010;
int q[N], s[N];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }
    
    int hh = 0, tt = -1;
    int res = -0x3f3f3f3f;
    
    for(int i = 1; i <= n; i++)
    {
        if(q[hh] < i - m) hh++;
        while(hh <= tt && s[q[tt]] >= s[i - 1]) tt--;
        q[++tt] = i - 1;
        res = max(res, s[i] - s[q[hh]]);
    }
    
    printf("%d\n", res);
    
    return 0;
}

1089. 烽火传递

  • 在某两个城市之间有 n n n 座烽火台,每个烽火台发出信号都有一定的代价。为了使情报准确传递,在连续 m m m 个烽火台中至少要有一个发出信号。现在输入 n , m n,m n,m 和每个烽火台的代价,请计算在两城市之间准确传递情报所需花费的总代价最少为多少。
  • 原本思路是 f ( i , j ) f(i,j) f(i,j),第 i i i 个烽火台状态为 j j j 时的代价。不过题解给的是 f ( i ) f(i) f(i) 表示 1 ∼ i 1 \sim i 1i 且点燃第 i i i 个烽火台的代价.
  • f ( i ) = min ⁡ i − m ≤ j < i { f ( j ) } + w ( i ) f(i) = \min\limits_{i - m \le j < i}\{f(j)\}+w(i) f(i)=imj<imin{f(j)}+w(i).
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int q[N], f[N], w[N];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
    }
    
    //这里,0应该是单调队列第一个元素,要作为状态转移的起点
    int hh = 0, tt = -1;
    q[++tt] = 0;
    for(int i = 1; i <= n; i++)
    {
        if(q[hh] < i - m) hh++;
        f[i] = f[q[hh]] + w[i];
        while(hh <= tt && f[q[tt]] >= f[i]) tt--;
        q[++tt] = i;
    }
    
    int ans = 0x3f3f3f3f;
    for(int i = max(1, n - m + 1); i <= n; i++) ans = min(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}

11. 斜率优化DP

12. 基环树DP

如果一张无向连通图包含恰好一个环,则称它是一棵 基环树 (Pseudotree)

如果一张有向弱连通图每个点的入度都为 1 1 1,则称它是一棵 基环外向树

如果一张有向弱连通图每个点的出度都为 1 1 1,则称它是一棵 基环内向树

多棵树可以组成一个 森林 (Forest),多棵基环树可以组成 基环森林 (Pseudoforest),多棵基环外向树可以组成 基环外向树森林,多棵基环内向树可以组成 基环内向森林 (Functional graph)

如果一张无向连通图的每条边最多在一个环内,则称它是一棵 仙人掌 (Cactus)。多棵仙人掌可以组成 沙漠

358. 岛屿

  • 在环上进行单调队列优化
  • 题意:你准备游览一个公园,该公园由 N N N 个岛屿组成,当地管理部门从每个岛屿出发向另外一个岛屿建了一座桥,不过桥是可以双向行走的。可证这是一个基环森林。现在求每个基环树的最长的两点之间路径之和。

算法模板(4):动态规划(2)

  • 这道题的思路是,找到每一个基环树上面的环,如果两个点位于同一个树上,那么就是树上的直径;如果两点分别位于两棵树上,如上图,那么答案就是 d x + d y + S x − S y d_x + d_y + S_x - S_y dx+dy+SxSy.
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010, M = N * 2;
typedef long long ll;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int n;
bool st[N];
int q[2 * N], ins[N]; //ins 表示在栈中
int fu[N], fw[N];  //u的父结点,以及与父结点之间的边权.
int cnt, cir[N], ed[N];
ll s[N], d[N * 2], sum[N * 2], ans;

void dfs_c(int u, int from)
{
    st[u] = ins[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(i == (from ^ 1)) continue;
        int v = e[i];
        fu[v] = u, fw[v] = w[i];
        if(!st[v]) dfs_c(v, i);
        else if(ins[v])
        {
            cnt++;
            ed[cnt] = ed[cnt - 1];
            ll sum = w[i];
            for(int k = u; k != v; k = fu[k])
            {
                s[k] = sum;
                cir[++ed[cnt]] = k;
                sum += fw[k];
            }
            s[v] = sum, cir[++ed[cnt]] = v;
        }
    }
    ins[u] = false;
}

ll dfs_d(int u)
{
    ll d1 = 0, d2 = 0;
    st[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if(st[v]) continue;
        ll dist = dfs_d(v) + w[i];
        if(dist >= d1) d2 = d1, d1 = dist;
        else if(dist > d2) d2 = dist;
    }
    ans = max(ans, d1 + d2);
    return d1;
}


int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(i, a, b), add(a, i, b);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!st[i]) dfs_c(i, -1);
    }

    memset(st, 0, sizeof st);
    for(int i = 1; i <= ed[cnt]; i++) st[cir[i]] = true;

    ll res = 0;

    for(int i = 1; i <= cnt; i++)
    {
        ans = 0;
        int sz = 0;
        for(int j = ed[i - 1] + 1; j <= ed[i]; j++)
        {
            int k = cir[j];
            d[sz] = dfs_d(k);
            sum[sz] = s[k];
            sz++;
        }

        for(int j = 0; j < sz; j++)
        {
            d[j + sz] = d[j], sum[j + sz] = sum[j] + sum[sz - 1];
        }

        int hh = 0, tt = -1;
        for(int j = 0; j < 2 * sz; j++)
        {
            if(hh <= tt && q[hh] < j - sz + 1) hh++;
            if(hh <= tt) ans = max(ans, d[j] + sum[j] + d[q[hh]] - sum[q[hh]]);
            while(hh <= tt && d[q[tt]] - sum[q[tt]] <= d[j] - sum[j]) tt--;
            q[++tt] = j;
        }
        res += ans;
    }

    printf("%lld\n", res);
    return 0;
}

1080. 骑士

  • 破环:基环树上的最大独立集问题

  • 从所有骑士 n ≤ 1 0 6 n \le 10^6 n106 中选出一个骑士军团,使得军团内没有矛盾的两人,即不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况,并且使这支骑士军团最富有战斗力。为描述战斗力,我们将骑士按照 1 1 1 N N N 编号,给每位骑士一个战斗力的估计,一个军团的战斗力为所有骑士的战斗力之和。每个骑士均有一个最痛恨的人。

  • 可以类比 没有上司的舞会,对于每一个基环树,我们找到环上的一个点 u u u,假设环上另一个点是 v v v,那么我们讨论一下 u u u v v v 之间是否要断开。断开意味着之前 u u u v v v 不能同时选但是现在可能会同时选了,只要避免掉这个情况就可以了. 如果不选 u u u 的话,那么这条边是否删掉后也不改变答案. 如果选 u u u 的话,由于 ( u , v ) (u,v) (u,v) 被删掉了,那么我们特判不选择 v v v 即可. 综上,我们删掉这条边之后,只需要不同时选 u u u v v v 即可.

  • 最后答案就是 max ⁡ { f ( u , 0 ) , f ( u , 1 ) } \max\{f(u, 0), f(u,1)\} max{f(u,0),f(u,1)}.

  • 所有出度都为1,是内向基环树,建反向边.

算法模板(4):动态规划(2)

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const int N = 1000010;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
int h[N], e[N], ne[N], w[N], idx, rm[N];
int n;
ll f1[N][2], f2[N][2], ans;
bool st[N], ins[N];
inline void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs_f(int u, int pa, ll f[][2])
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(rm[i]) continue;
        int v = e[i];
        dfs_f(v, pa, f);
        f[u][0] += max(f[v][0], f[v][1]);
    }
    
    f[u][1] = -INF;
    if(u != pa)
    {
        f[u][1] = w[u];
        for(int i = h[u];i != -1; i = ne[i])
        {
            if(rm[i]) continue;
            int v = e[i];
            f[u][1] += f[v][0];
        }
    }
}

void dfs_c(int u)
{
    st[u] = ins[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if(!st[v]) dfs_c(v);
        else if(ins[v])
        {
            rm[i] = 1;
            dfs_f(v, -1, f1);
            dfs_f(v, u, f2);
            ans += max(f1[v][0], f2[v][1]);
        }
    }
    ins[u] = false;
}


int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int v;
        scanf("%d%d", &w[i], &v);
        add(v, i);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!st[i]) dfs_c(i);
    }
    printf("%lld\n", ans);
    return 0;
}

13. 四边形不等式DP

基本概念

定义一:设 w ( x , y ) w(x,y) w(x,y) 是定义在整数集合上的二元函数。 ∀ a , b , c , d , a ≤ b ≤ c ≤ d , w ( a , d ) + w ( b , c ) ≥ w ( a , c ) + w ( b , d ) \forall a,b,c,d,a \le b \le c \le d,w(a,d) + w(b,c) \ge w(a,c) + w(b,d) a,b,c,d,abcd,w(a,d)+w(b,c)w(a,c)+w(b,d).

定义二:设 w ( x , y ) w(x,y) w(x,y) 是定义在整数集合上的二元函数。若对于定义域上的任意整数 a , b a,b a,b,其中 a < b a < b a<b,都有 w ( a , b + 1 ) + w ( a + 1 , b ) ≥ w ( a , b ) + w ( a + 1 , b + 1 ) w(a, b + 1) + w(a + 1,b)\ge w(a, b) + w(a + 1, b + 1) w(a,b+1)+w(a+1b)w(a,b)+w(a+1,b+1).
f l , r = min ⁡ k = l r − 1 { f l , k + f k + 1 , r } + w ( l , r ) ( 1 ≤ l < r ≤ n ) f_{l,r} = \min_{k=l}^{r-1}\{f_{l,k}+f_{k+1,r}\} + w(l,r)\qquad\left(1 \leq l < r \leq n\right) fl,r=k=lminr1{fl,k+fk+1,r}+w(l,r)(1l<rn)

直接简单实现状态转移,总时间复杂度将会达到 O ( n 3 ) O(n^3) O(n3),但当函数 w ( l , r ) w(l,r) w(l,r) 满足一些特殊的性质时,我们可以利用决策的单调性进行优化。

  • 区间包含单调性:如果对于任意 l ≤ l ′ ≤ r ′ ≤ r l \leq l' \leq r' \leq r llrr,均有 w ( l ′ , r ′ ) ≤ w ( l , r ) w(l',r') \leq w(l,r) w(l,r)w(l,r) 成立,则称函数 w w w 对于区间包含关系具有单调性。
  • 四边形不等式:如果对于任意 l 1 ≤ l 2 ≤ r 1 ≤ r 2 l_1\leq l_2 \leq r_1 \leq r_2 l1l2r1r2,均有 w ( l 1 , r 1 ) + w ( l 2 , r 2 ) ≤ w ( l 1 , r 2 ) + w ( l 2 , r 1 ) w(l_1,r_1)+w(l_2,r_2) \leq w(l_1,r_2) + w(l_2,r_1) w(l1,r1)+w(l2,r2)w(l1,r2)+w(l2,r1) 成立,则称函数 w w w 满足四边形不等式(简记为“交叉小于包含”)。若等号永远成立,则称函数 w w w 满足 四边形恒等式

引理 1:若 w ( l , r ) w(l, r) w(l,r) 满足区间包含单调性和四边形不等式,则状态 f l , r f_{l,r} fl,r 满足四边形不等式。

304. 诗人小G

2889. 再探石子合并

14. 插头DP

又叫轮廓线dp,是状态压缩dp的一种实现方式。一般都是基于一个网格,有连通性的限制。

2934. 插头DP

  • 给你一个 n × m n×m n×m 的棋盘,有的格子是障碍,问共有多少条回路满足经过每个非障碍格子恰好一次。

  • 每一个格子至多和上下左右四个格子相连,一条入边,一条出边,因此最多是6种经过这个格子的可能性。因此按照格子枚举复杂度比较低。我们从左到右,从上到下依次枚举格子,如图所示,红色线上方表示已经枚举过的格子,下方表示尚未枚举到的格子,红线拐弯的那个地方表示正在枚举的格子。我们看那个红线,表示边的信息。可以记录是否有边出来。然后记录连通块儿的信息,绿色的线连接的表示连通块儿。注意红线上每条小边也是有编号的,从 0 到 N N N N + 1 N + 1 N+1 条边。

  • f ( i , j , s ) f(i,j,s) f(i,j,s) 表示当前枚举到第 ( i , j ) (i,j) (i,j) 这个格子,轮廓线的状态是 s s s 的方案数。用括号表示法的话(左括号表示连通块儿的左半边,右括号表示连通块儿的右半边),没有括号是0,左括号是1,右括号是2,红线上的每一条小边有3个状态,因此可以采用 4 进制表示这条红线的状态 s。而且我们也发现,枚举的 ( i , j ) (i,j) (i,j) 的格子确定的话,方案数就确定了。

  • 插头dp的状态表示都是这个样子,但是状态转移很复杂。插头dp最难的地方就是状态转移的讨论。文章来源地址https://www.toymoban.com/news/detail-491792.html

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 50010, maxm = maxn * 2 + 7;

//合法状态大致不到五万个

int N, M, end_x, end_y;  //end_x, end_y 表示最后一个没有障碍的格子
int g[20][20], q[2][maxn], cnt[maxn];  //滚动状态数组,q 里面存的是有效状态在哈希表内的下标。
int h[2][maxm];   //滚动哈希表
ll v[2][maxm];

int find(int cur, int x)   //哈希表
{
    int t = x % maxm;
    while(h[cur][t] != -1 && h[cur][t] != x){
        if(++t == maxm) t = 0;
    }
    return t;
}

void insert(int cur, int state, ll w)
{
    int t = find(cur, state);
    if (h[cur][t] == -1)
    {
        h[cur][t] = state, v[cur][t] = w;
        q[cur][++cnt[cur]] = t;
    }
    else v[cur][t] += w;
}

int get(int state, int k)   //求第 k 个格子的状态,其实就是求state的4进制的意义下第 k 位数字。
{
    return (state >> (k * 2)) & 3;
}

int set(int k, int v)   //构造四进制下第k位数字为 v 的数
{
    return v * (1 << (k * 2));
}

int main()
{
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++){
        char str[20];
        scanf("%s", str + 1);
        for(int j = 1; j <= M; j++){
            if(str[j] == '.'){
                g[i][j] = 1;
                end_x = i, end_y = j;
            }
        }
    }
    ll res = 0;
    memset(h, -1, sizeof h);
    //将最开始的状态置为1
    int cur = 0;
    insert(cur, 0, 1);
    //cur表示滚动数组当前是哪一层。
    for (int i = 1; i <= N; i ++ )
    {
        for (int j = 1; j <= cnt[cur]; j ++ )
            h[cur][q[cur][j]] <<= 2;
        for (int j = 1; j <= M; j ++ )
        {
            int last = cur;
            cur ^= 1, cnt[cur] = 0;
            memset(h[cur], -1, sizeof h[cur]);
            for (int k = 1; k <= cnt[last]; k ++ )
            {
                int state = h[last][q[last][k]];
                ll w = v[last][q[last][k]];
                int x = get(state, j - 1), y = get(state, j);
                if (!g[i][j])
                {
                    //当前是障碍物
                    if (!x && !y) insert(cur, state, w);
                }
                else if (!x && !y)
                {
                    if (g[i + 1][j] && g[i][j + 1])
                        insert(cur, state + set(j - 1, 1) + set(j, 2), w);
                }
                else if (!x && y)
                {
                    if (g[i][j + 1]) insert(cur, state, w);  //状态不变
                    if (g[i + 1][j]) insert(cur, state + set(j - 1, y) - set(j, y), w);  //在j-1的位置减去插头y,在j的位置加上插头y
                }
                else if (x && !y)
                {
                    if (g[i][j + 1]) insert(cur, state - set(j - 1, x) + set(j, x), w);
                    if (g[i + 1][j]) insert(cur, state, w);
                }
                else if (x == 1 && y == 1)
                {
                    //开始括号匹配,找到最后一对匹配的括号,把他们俩连起来。
                    for (int u = j + 1, s = 1;; u ++ )
                    {
                        int z = get(state, u);
                        if (z == 1) s ++ ;
                        else if (z == 2)
                        {
                            if ( -- s == 0)
                            {
                                insert(cur, state - set(j - 1, x) - set(j, y) - set(u, 1), w);
                                break;
                            }
                        }
                    }
                }
                else if (x == 2 && y == 2)
                {
                    for (int u = j - 2, s = 1;; u -- )
                    {
                        int z = get(state, u);
                        if (z == 2) s ++ ;
                        else if (z == 1)
                        {
                            if ( -- s == 0)
                            {
                                insert(cur, state - set(j - 1, x) - set(j, y) + set(u, 1), w);
                                break;
                            }
                        }
                    }
                }
                else if (x == 2 && y == 1)
                {
                    insert(cur, state - set(j - 1, x) - set(j, y), w);
                }
                else if (i == end_x && j == end_y)
                    res += w;
            }
        }
    }
    printf("%lld\n", res);
    return 0;
}

到了这里,关于算法模板(4):动态规划(2)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法模板(4):动态规划(2)

    没有上司的舞会 树上最大独立集问题 Ural 大学有 N N N 名职员,编号为 1 ∼ N 1 sim N 1 ∼ N 。他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数,用整数 H i H_i H i ​ 给出,其中 1 ≤ i ≤ N 1 le i le N 1 ≤ i ≤ N 。现在要召开一场周年

    2024年02月09日
    浏览(34)
  • 【算法模板】动态规划,不可多得的干货

    ================================================================================ 📒 博客首页:铁甲小宝同学 📒 🌞文章目的: 动态规划基础篇分享 🌞 🙏博主也在学习阶段,如若发现问题,请告知,非常感谢🙏 💗 同时也非常感谢各位小伙伴们的支持 💗 🌈 每日一语:你相信光吗? 🌈

    2024年04月25日
    浏览(27)
  • 算法模板(4):动态规划(4) 做题积累(2)

    1. 1088. 旅行问题 John 打算驾驶一辆汽车周游一个环形公路。 公路上总共有 n 个车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。 John 必须从某个车站出发,一直按顺时针(或逆时针)方向走遍所有的车站,并回到起点。 在一开始的时候,

    2024年02月12日
    浏览(40)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(43)
  • 动态规划-树形DP

    链接:https://www.acwing.com/problem/content/848/ 给定一颗树,树中包含 n n n 个结点(编号 1 ∼ n 1 sim n 1 ∼ n )和 n − 1 n-1 n − 1 条无向边。 请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。 重心定义:重心是指树中的一个结点,如果将这个点删除后,剩

    2024年02月08日
    浏览(40)
  • 动态规划之树形DP

    树形DP是指在“树”这种数据结构上进行的动态规划:给出一颗树,要求以最少的代价(或取得最大收益)完成给定的操作。通常这类问题规模比较大,枚举算法效率低,无法胜任,贪心算法不能求得最优解,因此需要用动态规划进行求解。 在树上做动态规划显得非常合适,

    2024年02月05日
    浏览(45)
  • 动态规划——树形DP 学习笔记

    前置知识:树基础。 树形 DP,即在树上进行的 DP,最常见的状态表示为 (f_{u,cdots}) ,表示以 (u) 为根的子树的某个东东。 本文将讲解一些经典题目(树的子树个数、树的最大独立集、树的最小点覆盖、树的最小支配集、树的直径、树的重心、树的中心),以及一些常见形

    2024年02月08日
    浏览(38)
  • 动态规划报告(树形DP+概率DP

    树形 DP,即在树上进行的 DP。由于树固有的递归性质,树形 DP 一般都是递归进行的。一般需要在遍历树的同时维护所需的信息 以一道题目为例 2022CCPC桂林站G Group Homework No, we don’t want group homework. It’s the place where 1+11 can be true. However, you are currently the leader of a group with three

    2024年02月12日
    浏览(48)
  • 动态规划day09(打家劫舍,树形dp)

    目录 198.打家劫舍 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难 213.打家劫舍II 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难 337.打家劫舍 III(树形dp) 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中

    2024年01月23日
    浏览(94)
  • 【LeetCode动态规划#11】打家劫舍系列题(涉及环结构和树形DP的讨论)

    力扣题目链接(opens new window) 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非

    2023年04月21日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包