| 题目 | 类型 |
|---|---|
| 大盗阿福 | 状态机模型 |
| 股票买卖Ⅳ | 状态机模型 |
| 股票买卖Ⅴ | 状态机模型 |
| 设计密码 | 状态机模型 |
1、大盗阿福
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺，每家店中都有一些现金。
阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
输入格式 输入的第一行是一个整数 T ，表示一共有 T 组数据。 接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺。 第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。 每家店铺中的现金数量均不超过1000。 输出格式 对于每组数据，输出一行。 该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。 数据范围 1≤T≤50 , 1≤N≤105 输入样例： 2 3 1 8 2 4 10 7 6 14 输出样例： 8 24 样例解释 对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。 对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。
思路：
f[i][j]表示对于前i个店铺，j表示偷或者不偷，所产生的价值的集合，属性：最大值
每个店铺有两个状态:0和1分别表示不偷和偷，两个状态相互转换
两个状态：
第i个店铺被偷可以由第i-1个店铺不被偷转换过来
第i个店铺不被偷可以由第i-1个店铺偷或者不被偷转换过来
状态转移方程：
f[i][0] = max(f[i - 1][1], f[i - 1][0]);
f[i][1] = f[i - 1][0] + a[i];
代码：
#include<bits/stdc++.h>
using namespace std;
int t;
int n;
const int N=1e5+5,INF=0x3f3f3f3f;
int a[N];
int f[N][2];//f[i][j]中，i代表前i个金店的方案，j为1表示偷，j为0表示不偷
//转移方程：
//fi,1=fi−1,0+wi
//fi,0=max(fi−1,1,fi−1,0)
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];//输入每家金店的现金数量
}
//dp
f[0][0]=0;
f[0][1]=0;
for(int i=1;i<=n;i++)
{
f[i][0] = max(f[i - 1][1], f[i - 1][0]);
f[i][1] = f[i - 1][0] + a[i];
}
cout << max(f[n][0], f[n][1]) << endl;
}
return 0;
}
2、股票买卖Ⅳ
给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。
输入格式 第一行包含整数 N 和 k ，表示数组的长度以及你可以完成的最大交易笔数。 第二行包含 N 个不超过 10000 的非负整数，表示完整的数组。 输出格式 输出一个整数，表示最大利润。 数据范围 1≤N≤105 , 1≤k≤100 输入样例1： 3 2 2 4 1 输出样例1： 2 输入样例2： 6 2 3 2 6 5 0 3 输出样例2： 7 样例解释 样例1：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4)的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。 样例2：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.
思路：
f[i][j][k]表示前i天，交易次数为j，股票持有状态为k的方案的获得的价值（状态k == 0的时候，相当于完成了j笔交易，状态k == 1的时候，相当于正在进行第j笔交易）
属性：最大值
状态机表示：
空仓状态可以由持仓状态和空仓状态转移过来
持仓状态可以由持仓状态和空仓状态转移过来
注意卖出后才相当于一次交易
//空仓状态
f[i][j][0]=max(f[i-1][j][1]+a[i],f[i-1][j][0]);
//持仓状态
f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-a[i]);//卖出才构成一次完整的股票交易，所以从j-1开始转移
对于持仓状态转移方程的解释：
f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-a[i]);
可以从第j笔交易中的持仓状态转移过来，如果从持仓状态转移过来，可以直接在i-1天直接转移过来
如果从空仓转移过来，那需要买股票，意味着新的一笔交易开始了，j就相当于那一笔新的交易，那么上次空仓的状态（k == 0，如上文所述，状态k 0的时候，相当于完成了j笔交易，状态k == 1的时候，相当于正在进行第j笔交易）就相当于完成了j-1次交易，那就从j-1笔交易的状态转移过来
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int n,k;
int a[N];
int f[N][103][2];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}//读入股票在第i天的价格
memset(f,-0x3f,sizeof f);
for(int i=0;i<=n;i++)f[i][0][0]=0;//从0开始初始化
//dp
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
//空仓状态
f[i][j][0]=max(f[i-1][j][1]+a[i],f[i-1][j][0]);
//持仓状态
f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-a[i]);//卖出才构成一次完整的股票交易，所以从j-1开始转移
}
}
int res=0;
for(int i=1;i<=k;i++)res=max(res,f[n][i][0]);
cout<<res;
return 0;
}
3、股票买卖Ⅴ
给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
输入格式 第一行包含整数 N ，表示数组长度。 第二行包含 N 个不超过 10000 的正整数，表示完整的数组。 输出格式 输出一个整数，表示最大利润。 数据范围 1≤N≤105 输入样例： 5 1 2 3 0 2 输出样例： 3 样例解释 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]，第一笔交易可得利润 2-1 = 1，第二笔交易可得利润 2-0 = 2，共得利润 1+2 = 3。
思路：
这时候要用到三个状态了（前两题都是两个状态）
状态表示：
f[N][K]表示前i天的状态为k表示的价值的集合
属性：最大值
三个状态分别为：冷却期（不能买东西）、空仓期（空仓大于等于两天的情况，也是本题状态的入口，因为一开始也是可以直接买股票的）、持仓期
初始化：
把所有的状态都初始化为非法的（负无穷），只有一个合法状态那就是入口
用2表示空仓期、1表示冷却期、0表示持仓期
状态转移方程：
//空仓一天的情况
f[i][1]=f[i-1][0]+w[i];//上一支股票的持仓状态卖出
//空仓二天以及以上的情况
f[i][2]=max(f[i-1][2],f[i-1][1]);
//持仓的情况
f[i][0]=max(f[i-1][0],f[i-1][2]-w[i]);
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int w[N];
int n,m;
int f[N][3];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
//dp
int res=0;
memset(f,-0x3f,sizeof f);
f[0][2]=0;
for(int i=1;i<=n;i++)
{
//空仓一天的情况
f[i][1]=f[i-1][0]+w[i];//上一支股票的持仓状态卖出
//空仓二天以及以上的情况
f[i][2]=max(f[i-1][2],f[i-1][1]);
//持仓的情况
f[i][0]=max(f[i-1][0],f[i-1][2]-w[i]);
//cout<<f[i][0]<<" "<<f[i][2]<<" "<<f[i][1]<<endl;
//res=max(f[i][2],f[i][1]);
}
cout<<max(f[n][2],f[n][1]);
//cout<<res;
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 的长度。 输入样例1： 2 a 输出样例1： 625 输入样例2： 4 cbc 输出样例2： 456924
思路：
即密码串中不能包含给定的模式串
结合kmp算法可得，若模式串的长度为m，则对于每一位密码总共有26种允许的（但不一定存在的）匹配状态
分别为不和子串有任何匹配（0表示不匹配）、匹配到第一个位置、匹配到第二个位置…匹配到第m-1个位置（因为匹配到m就包含这个模式串了，所以说不能匹配到第m个位置）
f[i][j]表示已经生成i位密码，匹配到模式串的位置为j（0表示不匹配）的状态的方案数量
步骤：
1、先处理出模式串的next表
2、进行状态机的转换
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=53;
int f[N][N];
int ne[N];//next数组
char str[N];//字串
const int mod=1e9+7;
int main()
{
int n,m;
cin>>n>>str+1;
m=strlen(str+1);
//kmp求next表模板
for(int i=2,j=0;i<=m;i++)
{
//不匹配的情况
while(j && str[j+1]!=str[i])
{
j=ne[j];
}
//匹配的话则最大公共前后缀+1
if(str[j+1]==str[i])j++;
//给next表赋值
ne[i]=j;
}
//dp+状态机
f[0][0]=1;//已经匹配了0位，且匹配到的字符串位置（状态）是0的方案数
for(int i=0;i<n;i++)//枚举密码位
{
for(int j=0;j<m;j++)//枚举第i位密码在模板串中的位置
{
for(int k='a';k<='z';k++)//枚举第i+1位的字符
{
//匹配过程:寻找当第i+1的位置是k时,并且密码已经生成了第i位,已经匹配的子串的位置是j时,能跳到哪个位置
int u=j;
while(u && str[u+1]!=k)u=ne[u];
if(str[u+1]==k)u++;
if(u<m)f[i+1][u]=(f[i+1][u]+f[i][j])%mod;//因为不能包含字串，所以不能等于m
}
}
}
int res=0;
for(int i=0;i<m;i++) res=(res+f[n][i])%mod;
//将所有的方案数加起来即为总方案数
printf("%d",res);
return 0;
}
