文章目录
- 一、大盗阿福
- 二、股票买卖 IV
- 三、股票买卖 V
- 四、设计密码
- 4.1kmp题目
- 4.2设计密码
一、大盗阿福
题目链接
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int f[N][2];
int main()
{int t, n;cin >> t;while(t --){cin >> n;for(int i = 1;i <= n;i ++){//f[i, 0]表示不抢第i家店铺//f[i ,1]表示要抢第i家店铺int money;cin >> money;f[i][0] = max(f[i - 1][0],f[i - 1][1]);f[i][1] = f[i - 1][0] + money;}printf("%d\n",max(f[n][0],f[n][1]));}return 0;
}
二、股票买卖 IV
题目链接
对于状态机模型来说,你刚开始所处的位置初始化为0(一般来说),其他位置一般初始化为无穷大,对于该题来说你要初始化为负无穷
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10, INF = 1e9, M = 110;
int n,k;
int f[N][M][2];int main()
{cin >> n >> k;memset(f, -0x3f, sizeof f);for (int i = 0; i <= n; i ++ ) f[i][0][0] = 0;//j为0时代表你一次交易没有完成for(int i = 1;i <= n;i ++){int m;cin >> m;for(int j = 1;j <= k;j ++){f[i][j][0] = max(f[i - 1][j][1] + m, f[i - 1][j][0]);f[i][j][1] = max(f[i - 1][j - 1][0] - m,f[i - 1][j][1]);}}int res = 0;for(int i = 1;i <= k;i ++) res = max(res, f[n][i][0]);cout << res;return 0;
}
三、股票买卖 V
题目链接
这个题加了一个冷冻期的状态,其实和上一题差不多,没什么区别
多加了一种状态而已
入口是冷冻期
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int f[N][3];
int n;int main()
{memset(f, -0x3f, sizeof f);f[0][2] = 0;//1代表你处于卖出状态,2代表你处于冷冻期cin >> n;for(int i = 1;i <= n;i ++ ){int w;cin >> w;f[i][0] = max(f[i - 1][2] - w, f[i - 1][0]);f[i][1] = f[i - 1][0] + w;f[i][2] = max(f[i - 1][1],f[i - 1][2]);}cout << max(f[n][1],f[n][2]);return 0;
}
四、设计密码
4.1kmp题目
这个题要用到kmp,先说说kmp,抽象理解,简写代码
具体理解请看我的这篇博客(kmp算法细节详解)
首先我们要理解kmp是算法的作用是进行子串的匹配,也就是根据子串的前缀和后缀最大能够匹配的字符串个数
图解:
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1e5 + 10, M = 1e6 + 10;
char p[N], s[M];
int ne[N];int main()
{int n,m;cin >> n >> p + 1 >> m >> s + 1;//先求模式串next数组for(int i = 2, j = 0;i <= n;i ++){while(j && p[i] != p[j + 1]) j = ne[j];if(p[i] == p[j + 1]) j ++;ne[i] = j;//j 前面是前缀,后面到i是后缀}for(int i = 1, j = 0;i <= m;i ++)//遍历主串{while(j && s[i] != p[j + 1]) j = ne[j];if(s[i] == p[j + 1]) j ++;if(j == n){printf("%d ", i - n);j = ne[j];}}return 0;
}
4.2设计密码
题目链接
题解摘自E.lena
在这里插入图片描述
这里f[i + 1][u] 为什么还要加上自己,因为这个f[i + 1][u] 可能含有由其他状态转移转移过来
#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N=55,mod=1e9+7;int f[N][N],ne[N];
char str[N];//子串int main()
{int n,m;cin>>n>>str+1;m=strlen(str+1);for(int i=2,j=0;i<=m;i++)//求出ne数组(kmp模板){while(j&&str[j+1]!=str[i]) j=ne[j];if(str[j+1]==str[i]) j++;ne[i]=j;}f[0][0]=1;//已经匹配了0位,且匹配的子串的位置是0时的方案数为1;(初始化)for(int i=0;i<n;i++)//枚举密码位for(int j=0;j<m;j++)//把第i位密码匹配到的子串位置都枚举一遍//j表示第i位密码匹配到的位置,因为不能包含子串,所以不能匹配到m这个位置for(char 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;//因为是从f[i][j](i+1的位置为k)跳到f[i+1][u]这个位置,所以f[i+1][u]=f[i+1][u]+f[i][j];/*注:可能存在重边,因为j不同但ne[j]是相同的,并且k是相同的,所以此时f[i][j1]和f[i][j2]跳到的位置是一样的(k相同,ne[j1]=ne[j2])*/}int res=0;for(int i=0;i<m;i++) res=(res+f[n][i])%mod;//将所有的方案数加起来即为总方案数printf("%d",res);return 0;
}