寒假思维训练day10 浅谈状态机DP

发布时间:2024年01月17日

带状态机的动态规划:

一、状态机DP的本质,状态机DP的理论部分:

1、本质(我自己对它的浅薄认识):当事物只有有限个状态,并且每个状态的联系形成的图是一个拓扑图,我们就可以用具有后效性(或者是前效性)的拓扑序解决这个问题(即用动态规划线性解出答案)。

2、状态的表示:f\left [ i \right ]\left [ state \right ],表示考虑第i个事物时,事件处于state的状态的答案。

3、状态计算:f\left [ i \right ]\left [state1 \right ] = (f\left [ i - 1 \right ]\left [ state1 \right ], f\left [ i - 1\right ]\left [ state2 \right ], ...) + w,括号表示:max或者min。

4、如果将每个状态连成图,必须具备拓扑序,这样才能线性扫描出答案。


二、例题以及解释:

例1:Problem - 455A - Codeforces

?(1)、题意: 给定一个长度为N(1 <= N <= 1e5)的序列a,元素a[i]满足1 <= a[i] <= 1e5,每次可以进行以下操作:选择目标a[i], 则可以使得分ans += a[i], 并且删除队伍中所有值为a[i] - 1,a[i] + 1的值。

?(2)、题解很显然,需要先进行排序,然后将值相同的看成一个块,再进行考虑,先考虑贪心,我们可以发现每个相邻的块都会有不同的情况,差值是1,或者是差值不为1,所以情况很多,我们无法知道后一个取什么或者前面取什么可以使得结果最优,显然需要DP,看一下这道题怎么用状态机DP去解决:

?(3)、DP求解:

方程的定义(状态的表示): DP[i][0]: 取i的值? ? ?DP[i][1]: 不取i的值状态的转移先要考虑前后数字的关系,如果当前数考虑DP[i][1],且后一个数与它的差值为1,DP[i - 1][1]必然不能转移过来,不然就矛盾了,因为选了i - 1必然会删除i, 所以此时DP[i][1] = dp[i -?1][0] + v

?(4)、转移代码:
?

a = sorted(a)
if a[i] - a[i - 1] == 1:
    dp[i][1] = dp[i - 1][0] + v
else: 
    dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]) + v 

dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]) 


(5)、最终代码:
?

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e6 + 10; 
int n; 
int a[N]; 
int cnt[N]; 
int f[N][2];  
namespace Calc {}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i], cnt[a[i]] = 0;
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i ++ ) cnt[a[i]] ++; 
    vector<int> us;
    us.push_back(-1);
    for(int i = 1; i <= n; i ++ ) {
        int j = i; 
        while(j + 1 <= n && a[j + 1] == a[i]) ++ j; 
        us.push_back(a[i]);
        i = j;    
    }
    memset(f, -0x3f, sizeof f); 
    f[0][0] = 0; 
    // cout << us.size() << endl; 
    
    for(int i = 1; i < us.size(); i ++ ) {
        if(us[i] - us[i - 1] == 1) {
            f[i][1] = f[i - 1][0] + us[i] * cnt[us[i]]; 
            f[i][0] = max(f[i - 1][0], f[i - 1][1]); 
        }
        else {
            f[i][1] = max(f[i - 1][0], f[i - 1][1]) + us[i] * cnt[us[i]]; 
            f[i][0] = max(f[i - 1][0], f[i - 1][1]); 
        }
    }
    cout << max(f[us.size() - 1][1], f[us.size() - 1][0]) << endl; 
}
signed main() {
    int ts = 1;
    // cin >> ts;
    while(ts --) solve();
    
    return 0;
}


例2:Problem - 545C - Codeforces

(1)、题意:沿着道路有n棵树,它们的坐标分别为x1,?x2,?...,?xn。每棵树都有它的高度h[i]。伐木工人可以砍倒一棵树并使其倒向左或右。之后,树将占据区间[xi?-?hi,?xi]或[xi, xi?+?hi]之一(闭区间)。没有被砍倒的树将占据坐标xi的一个点。伐木工人可以砍倒一棵树,前提是树倒下后占据的区间不包含任何被占据的点,问最多可以砍多少棵树。

(2)、题解:显然这道题的情况非常多,很难去贪心,这种情况不妨多往图论、DP方面去多想想,现在我们考虑一下如何用状态机DP去解决这个问题:


(3)、DP求解:

方程定义:DP[i][0], 将第i棵树砍到往左,DP[i][1] 不砍第i棵树,DP[i][2] 砍第i颗树往右边。

方程转移:
我们先要处理好两个边界,假设x[0]是负无穷,x[n + 1]是正无穷,它们的h[i] = 0,并且x[i], h[i] >= 1,默认1到n升序排列,这样子就可以探讨了,从前往后考虑(py伪代码):

考虑dP[i][0], 也就是砍倒第i颗树往右倒:
if a[i] - b[i] > a[i - 1] + b[i - 1]:
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][0], dp[i - 1][2]) + 1
else:
    if a[i] - b[i] > a[i - 1]: dp[i][0] = max(dp[i - 1][1], d[i - 1][0]) + 1
    else: dp[i][0] = -1e18 (无解)


考虑dp[i][1], 也就是不砍第i颗树:
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0], dp[i - 1][2]) 


考虑dp[i][2], 也就是砍到第i颗树向右:
if a[i] + b[i] < a[i + 1]: dp[i][2] = max(dp[i - 1][1], dp[i - 1][0], dp[i - 1][2]) + 1 
else: dp[i][2] = -1e18(无解)

(4)、答案代码:

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 10; 
int n, m;
int a[N], b[N]; 
int f[N][3]; 

// f[i][0] 左 
// f[i][1] 不放
// f[i][2] 右
int max(int x, int y, int z) {
    return max(max(x, y), z); 
}
void solve() {
   
    cin >> n;
    a[0] = -1e18, a[n + 1] = 1e18; 
    for(int i = 1; i <= n; i ++ ) 
        cin >> a[i] >> b[i]; 
    for(int i = 1; i <= n; i ++ ) {
        // f[i][0] 往左
        if(a[i] - b[i] > a[i - 1] + b[i - 1]) f[i][0] = max(f[i - 1][1], f[i - 1][0], f[i - 1][2]) + 1;
        else {
            if(a[i] - b[i] > a[i - 1]) f[i][0] = max(f[i - 1][1], f[i - 1][0]) + 1; 
            else f[i][0] = -1e18;
        }
        
        // f[i][1] 不动
        f[i][1] = max(f[i - 1][1], f[i - 1][0], f[i - 1][2]); 
        
        // f[i][2] 往右
        if(a[i] + b[i] < a[i + 1]) f[i][2] = max(f[i - 1][1], f[i - 1][0], f[i - 1][2]) + 1; 
        else f[i][2] = -1e18; 
    }
    
    cout << max(0ll, max(f[n][1], f[n][0], f[n][2])) << endl;
}
signed main() {
    int ts = 1;
    // cin >> ts;
    while(ts --) solve();
    
    return 0;
}

文章来源:https://blog.csdn.net/m0_74847145/article/details/135645640
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。