算法竞赛备赛进阶之状态机模型训练

目录

1.大盗阿福

2.股票买卖IV

3.股票买卖V

4.设计密码

---

算法状态机（ASM）图是一种描述时序数字系统控制过程的算法流程图，其结构形式类似于计算机中的程序流程图。

ASM图是用一些特定符号按规定的连接方式来描述数字系统的功能。应用ASM图设计数字系统，可以很容易将语言描述的设计问题变成时序流程图的描述，只要描述逻辑设计问题的时序流程图一旦形成，状态函数和输出函数就容易获得，从而得出相应的硬件电路。

1.大盗阿福

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

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

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

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

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

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

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

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

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

#include
#include
#include
​
using namespace std;
​
const int N = 100010, INF = 0x3f3f3f3f;
​
int n;
int w[N], f[N][2];
​
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> 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 - 1][0] + w[i];
        }
        
        printf("%d\n", max(f[n][0], f[n][1]));
    }
    
    return 0;
}

2.股票买卖IV

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

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

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

输入格式

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

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

#include
#include
#include
​
using namespace std;
​
const int N = 100010, M = 110, INF = 0x3f3f3f3f;
​
int n, m;
int f[N][M][2], w[N];
​
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++)
        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;
}

3.股票买卖V

#include
#include
#include
​
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][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]);
    }
    
    printf("%d\n", max(f[n][1], f[n][2]));
    
    return 0;
}

4.设计密码

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

1. S的长度是N

2. S质包含小写英文字母

3. S不包含子串T

例如abc和abcde是abcde的子串，adb不是abcde的子串

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

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

输入格式：

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

第二行输入字符串T，T中质保函小写字母。

#include
#include
#include
​
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;
}