状态机DP

概述

状态机模型包含多个待选状态，不同的状态之间有相互转化的方法，我们可以借助这些转化的手段，达成状态之间的相互转移，一般需要利用图论的知识进行转化

例1.大盗阿福

题目链接

题目描述

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 N 家店铺，每家店中都有一些现金。

阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。

作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。

他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

输入格式

输入的第一行是一个整数 T，表示一共有 T 组数据。

接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺。

第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。

每家店铺中的现金数量均不超过1000。

输出格式

对于每组数据，输出一行。

该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。

数据范围

\(1≤T≤50,\)

\(1≤N≤10^5\)

输入样例

输出样例

8
24

题解

考虑如何表示当前的状态，假设当前到第i家店铺，我们有偷和不偷两种状态，\(f[i,1]\)表示偷，\(f[i,0]\)表示不偷，则状态转移方程如下：

\(f[i,0]=max(f[i-1,0],f[i-1,1])\),当前不偷则上一家可偷可不偷
\(f[i,1]=f[i-1,0]+w[i]\),当前偷则上一家不偷

最后结果为第n家偷或不偷取最大

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int dp[N][2];
int a[N];
signed main() {
    int t;
    cin >> t;
    while(t -- ) {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i ++ ) {
            cin >> a[i];
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + a[i];
        }
        cout << max(dp[n][0], dp[n][1]) << '\n';
    }
    return 0;
}

例2.股票买卖 IV

题目链接

题目描述

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。

输入格式

第一行包含整数 N 和 k，表示数组的长度以及你可以完成的最大交易笔数。

第二行包含 N 个不超过 10000 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

\(1≤N≤10^5,\)

\(1≤k≤100\)

输入样例

6 2
3 2 6 5 0 3

输出样例

题解

考虑状态如何表示，对于第i天，有持仓和空仓两种状态，显然这里需要两维，但交易次数显然需要一维，因此我们定义\(f[i,j,k]\)为：第i天已经完成j笔交易并且第i天初始状态为k所得的最大利润，状态转移方程如下：

\(f[i,j,0]=max(f[i-1,j,0],f[i-1,j-1,1]+w[i])\)
\(f[i,j,1]=max(f[i-1,j,1],f[i-1,j,0]-w[i])\)

注意当j为0时特判\(f[i,j,0]\)

代码

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N = 1e5 + 5, M = 105;
int dp[N][M][2];
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0][0] = 0;
    for(int i = 1; i <= n; i ++ ) {
        int a;
        cin >> a;
        for(int j = 0; j <= k; j ++ ) {
            dp[i][j][1] = max(dp[i - 1][j][0] - a, dp[i - 1][j][1]);
            if(j)
                dp[i][j][0] = max(dp[i - 1][j - 1][1] + a, dp[i - 1][j][0]);
            else dp[i][j][0] = dp[i - 1][j][0];
        }
    }
    int res = 0;
    for(int i = 0; i <= k; i ++ ) res = max(res, dp[n][i][0]);
    cout << res;
    return 0;
}

例3.股票买卖 V

题目链接

题目描述

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

输入格式

第一行包含整数 N，表示数组长度。

第二行包含 N 个不超过 10000 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

\(1≤N≤105\)

输入样例

5
1 2 3 0 2

输出样例

题解

比上题新增加了冷冻期的条件，因此状态也要相应地增加，我们令\(f[i,0]\)表示第i天空仓且处于冷冻期，\(f[i,1]\)表示第i天空仓不处于冷冻期，\(f[i,2]\)表示第i天持仓，状态转移方程如下：

\(f[i,0]=f[i-1,2] + w[i]\)
\(f[i,1]=max(f[i-1,0], f[i-1,1])\)
\(f[i,2]=max(f[i-1,2],f[i-1][1]-w[i]\)

代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int n;
int w[N];
int f[N][3];

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    f[0][0] = f[0][2] = -INF, f[0][1] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        f[i][0] = f[i - 1][2] + w[i];
        f[i][1] = max(f[i - 1][0], f[i - 1][1]);
        f[i][2] = max(f[i - 1][2], f[i - 1][1] - w[i]);
    }

    printf("%d\n", max(f[n][0], f[n][1]));

    return 0;
}

例4.设计密码

题目链接

题目描述

你现在需要设计一个密码 S，S 需要满足：

S 的长度是 N；
S 只包含小写英文字母；
S 不包含子串 T；

例如：abc 和 abcde 是 abcde 的子串，abd 不是 abcde 的子串。

请问共有多少种不同的密码满足要求？

由于答案会非常大，请输出答案模 109+7 的余数。

输入格式

第一行输入整数N，表示密码的长度。

第二行输入字符串T，T中只包含小写字母。

输出格式

输出一个正整数，表示总方案数模 109+7 后的结果。

数据范围

\(1≤N≤50,\)

\(1≤|T|≤N\)，|T|是T的长度。

输入样例

4
cbc

输出样例

题解

对于单母串和单模式串匹配，很容易联想到KMP，对于本题，母串中不含模式串其实就是j走不到模式串的终点，根据KMP算法的特点，我们发现每次j的移动都是与母串当前位置的值一一对应，因此若枚举母串每一个位置的字母值，则j有26种跳跃方法。根据图论的相关知识，最终建出的图应该是有m个顶点，每个点有26条连向其他点的边构成的图，最终答案为j未跳到模式串末尾的方案数之和

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 55, mod = 1e9 + 7;
int f[N][N];
int ne[N];
string s;
int main() {
    int n;
    cin >> n >> s;
    int len = s.size();
    s = " " + s;
    for(int i = 2, j = 0; i <= len; i ++ ) {
        while(j && s[j + 1] != s[i]) j = ne[j];
        if(s[j + 1] == s[i]) j ++ ;
        ne[i] = j;
    } // 求next数组

    f[0][0] = 1;
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 0; j < len; j ++ ) {
            for(char k = 'a'; k <= 'z'; k ++ ) {
                int u = j;
                while(u && s[u + 1] != k) u = ne[u];
                if(s[u + 1] == k) u ++ ;
                if(u < len) f[i][u] = (f[i][u] + f[i - 1][j]) % mod; // j未跳到终点则状态转移
            }
        }
    }

    int res = 0;
    for(int i = 0; i < len; i ++ ) {
        res += f[n][i];
        res %= mod;
    }
    cout << res;
    return 0;
}