大盗阿福题目链接

1049. 大盗阿福 - AcWing题库

大盗阿福题目类型

状态机

大盗阿福题目思路

f(i)表示前i家的最大收益

动态规划

• 状态表示f[i, 0], f[i, 1]

  • 集合：所有走了i步，且当前位于状态j的所有走法

  • 属性：Max

• 状态计算

  • f[i,0]=max(f[i-1,0], f[i-1, 1])

  • f[i,1]=f[i-1, 0]+w[i]

大盗阿福代码

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 100010, INF = 0x3f3f3f3f;
​
int n;
int w[N],f[N][2];
int main(){
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&w[i]);
        f[0][0] = 0, f[0][1]=-INF;
        for(int i=1;i<=n;i++)
        {
            f[i][0]=max(f[i-1][0],f[i-1][1]);
            f[i][1]=f[i][0]+w[i];
        }
        
        printf("%d\n",max(f[n][0],f[n][1]));
    }
    return 0;
}

股票买卖IV题目链接

1057. 股票买卖 IV - AcWing题库

股票买卖IV题目类型

状态机

股票买卖IV题目思路

动态规划

• 状态计算

  • 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])

股票买卖IV代码

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 100010, M = 110, INF = 0x3f3f3f3f;
​
int n, m;
int w[N];
int f[N][M][2];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    memset(f, -0x3f, sizeof(f));
    for(int i=0;i<=n;i++)
    {
        scanf("%d",&w[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]);
    }
    printf("%d\n",res);
    return 0;
}

股票买卖V题目链接

1058. 股票买卖 V - AcWing题库

股票买卖V题目类型

状态机

股票买卖V题目思路

动态规划

• 状态计算

  • 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, 1], f[i-1, 2])

股票买卖V代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
​
const int N = 100010, INF = 0x3f3f3f3f;
​
int n;
int f[N][3];
int w[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>w[i];
    }
    f[0][0] = f[0][1] = -INF;
    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][1], f[i-1][2]);
    }
    cout << max(f[n][1],f[n][2]) <<endl;
    return 0;
}

设计密码题目链接

1052. 设计密码 - AcWing题库

设计密码题目类型

状态机+kmp算法

设计密码题目思路

动态规划

• 状态计算

  • f[i, j]表示当前已经写到了原字符串的第i个字母，当前跳到了kmp第j个状态的时候的所有方案数量

设计密码代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
​
const int N = 55, mod = 1e9 + 7;
​
int n, m;
char str[N];
int f[N][N];
int main()
{
    cin >> n >> str + 1;
    m = strlen(str + 1);
    
    int next[N] = {0};
    for(int i=2,j=0;i<=n;i++)
    {
        while(j && str[i]!=str[j+1]) j = next[j];
        if(str[i]==str[j+1]) j++;
        next[i] = j;
    }
    f[0][0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            for(char k = 'a';k<='z';k++)
            {
                int u=j;
                while(u&&k!=str[u+1]) u = next[u];
                if(k == 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;
}