状态机模型DP

//http://ybt.ssoier.cn:8088/problem_show.php?pid=1302

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int dp[N][3][3],n,w[N],t;
int main()
{
    cin>>t;
    while(t--){
        cin>>n;
        int res=0;
        memset(dp,-0x3f,sizeof dp);
        for(int i=1;i<=n;i++) cin>>w[i];
        for(int i=0;i<=n;i++) dp[i][0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=2;j++){
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+w[i]);
                dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-w[i]);
            }
        }
        cout << max(dp[n][0][0], max(dp[n][1][0], dp[n][2][0])) << endl;
        //注意这里,要把三种情况都判断,只买一次的情况是,再买第二次就亏了,所以买了直接卖出,这种算第一次的最大值 
    }
    return 0;
}

//https://www.acwing.com/problem/content/1059/

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dp[N][101][2],n,m,k,res,w[N];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    memset(dp,-0x3f,sizeof dp);
    for(int i=0;i<=n;i++) dp[i][0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+w[i]);
            dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-w[i]);
        }
    }
    for(int i=0;i<=m;i++) res=max(res,dp[n][i][0]);
    cout<<res<<endl;
    return 0;
}

//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

// dp[i][j],0为当前有票,1为没票的第一天,2为没票的第二天或更多天 

#include<bits/stdc++.h>
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int dp[100001][3],res=0,w[100001];
        memset(dp,0,sizeof dp);
        for(int i=0;i<n;i++) w[i+1]=prices[i];
        dp[0][0]=dp[0][1]=-0x3f3f3f3f;
        dp[0][2]=0;
        for(int i=1;i<=n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][2]-w[i]);
            dp[i][1]=dp[i-1][0]+w[i];
            dp[i][2]=max(dp[i-1][1],dp[i-1][2]);
        }
        return max(dp[n][1],dp[n][2]);
    }
};

//题目：
//你现在需要设计一个密码 S，S 需要满足：
//
//S 的长度是 N；
//S 只包含小写英文字母；
//S 不包含子串 T；
//例如：abc 和 abcde 是 abcde 的子串，abd 不是 abcde 的子串。
//请问共有多少种不同的密码满足要求？
//由于答案会非常大，请输出答案模 10e9+7 的余数。
//
//输入格式
//第一行输入整数N，表示密码的长度。
//第二行输入字符串T，T中只包含小写字母。
//
//输出格式
//输出一个正整数，表示总方案数模 10e9+7 后的结果。
//
//数据范围
//1≤N≤50,
//1≤|T|≤N，|T|是T的长度。
//
//输入:
//2
//a
//1
//2
//3
//输出：
//625

#include<bits/stdc++.h>
using namespace std;
const int N=55,mod=1e9+7;
int dp[N][N],n,m,ne[N],res;
char str[N];
int main()
{
    cin>>n>>str+1;
    m=strlen(str+1);
    for(int i=2,j=0;i<=n;i++){
        while(j&&str[i]!=str[j+1]) j=ne[j];
        if(str[i]==str[j+1]) j++;
        ne[i]=j;
    }
    dp[0][0] = 1;  //初始化，对于第0位密码，且匹配字串的位置为0时的方案数为1
    for(int i=0;i<n;i++){//枚举密码长度
        for(int j=0;j<m;j++){//枚举密码长度为i，且子串s匹配的位置为j时的状态,
            for(char k='a';k<='z';k++){//对于第i+1位字母，枚举26种可能的情况,
                //当前密码位数为i，且子串匹配的位置是j，尝试用i+1为k的情况进行跳转,
                //1.如果u能够跳转到子串s的最后一位(u==m)，说明密码第i+1位为k时，密码中会包含子串s,
                //2.反之则说明当密码的i+1位为k时不会包含子串s (u<m)，也就是合法方案，可以进行更新,
                int u=j;
                while(u&&k!=str[u+1]) u=ne[u];
                if(k==str[u+1]) u++;
                if(u<m) dp[i+1][u]=(dp[i+1][u]+dp[i][j])%mod;
            }
        }
    }
    for(int i=0;i<m;i++) res=(res+dp[n][i])%mod;
    cout<<res;
    return 0;
}