状态机模型——将难以直接描述的状态换成多维状态来表示

AcWing 1049. 大盗阿福

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5+10;

int f[N][2];
int w[N],n;

int main()
{
    int T;
    cin >> T;

    while(T--)
    {
        cin >> n;
        for(int i=1;i<=n;i++)cin >> w[i];
        memset(f,-0x3f,sizeof f);//按照实际含义来划分的话可以赋初值
        f[0][0]=0;

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

AcWing 1057. 股票买卖 IV

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

using namespace std;

const int N = 110, M = 1e5+10;

int f[M][N][2];
int w[M];
int n,m;

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin >> w[i];

    memset(f,-0x3f,sizeof f);
    for(int i=0;i<n;i++)f[i][0][0]=0;

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

    int res=0;
    for(int i=0;i<=m;i++)res=max(res,f[n][i][0]);
    cout << res << endl;
    return 0;
}

AcWing 1058. 股票买卖 V

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e5+10;

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

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)cin >> w[i];
    memset(f,-0x3f,sizeof f);
    f[0][2]=0;

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

AcWing 1052. 设计密码
由kmp和状态机结合而成
kmp:最大的前缀等于后缀，首先预处理next[N]数组
f[n][m]表示的是长度为n的字符串其中目标串的长度为m的长度

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

using namespace std;

const int N = 60,mod=1e9+7;

int f[N][N];
int n,m,ne[N];
char str[N];

int main()
{
    cin >> n >> str+1;
    m=strlen(str+1);
    f[0][0]=1;

    for(int i=2,j=0;i<=m;i++)
    {
        while(j&&str[i]!=str[j+1])j=ne[j];
        if(str[i]==str[j+1])j++;
        ne[i]=j;
    }

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        //kmp的性质，一般都是从下一位开始枚举
            for(char s='a';s<='z';s++)
            //穷举每一位选的字母
            {
                int u=j;
                while(u&&s!=str[u+1])u=ne[u];
                if(s==str[u+1])u++;
                if(u<m)f[i+1][u]=(f[i+1][u]+f[i][j])%mod;
            }

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