状态机dp
作者:
做ac梦w
,
2022-07-20 23:23:45
,
所有人可见
,
阅读 223
状态机dp
1.大盗阿福 在数组中取数 不能取连续两个 求max-sum 设dp[i][0]表示不取i位置的max dp[i][1]表示取i位置的max
dp[i][0]=max(dp[i-1][1],dp[i-1][0])
dp[i][1]=dp[i-1][0]+a[i];
2.股票买卖VI: 求最多j笔交易的最大收益
#include <iostream>
#include <cstring>
using namespace std;
const int N=1e5+10,M=110;
int dp[N][M][2],a[N];
int n,k;
//dp[i][j][0]表示在第i天(已经过了) 已经做过j次交易 手上没有股票的状态
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
memset(dp,-0x3f,sizeof dp);
dp[0][0][0]=0;
for(int i=1;i<=n;i++) dp[i][0][1]=max(dp[i-1][0][1],-a[i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][1]+a[i]);//卖出作为一次交易
dp[i][j][1]=max(dp[i-1][j][0]-a[i],dp[i-1][j][1]);
//cout<<dp[i][j][0]<<" "<<dp[i][j][1]<<endl;
}
}
int ans=0;
for(int i=0;i<=k;i++) ans=max(ans,dp[n][i][0]);
cout<<ans;
}
股票买卖V:含冷冻期:设dp[i][0]表示手中有股票 dp[i][1]表示手中无股票的第一天 dp[i][1]表示手中没股票的>1天
设计密码:kmp+状态机dp
题意 问长度为n的不包含子串的字符串方案个数
设dp[i][j]为已经枚举到第i个字符 已经匹配了j个字符的方案数
枚举第i+1个字符x 做kmp匹配 看一下能否匹配完模式串的m个字符 如果匹配完就continue;
否则用dp[i][j]更新dp[i+1][k];
代码:
#include <iostream>
using namespace std;
const int N = 55, mod = 1e9 + 7;
//输出n和s n是要构造的字符串长度 s是不能包含的字串
int n;
string s;
int dp[N][N];//表示枚举到第i个字母 已经匹配了j个字母的方案数 只要不匹配m个字母就表示不包含子串 就可以转移
int ne[N];
int main()
{
cin >> n >> s;
int m = s.size();
s = ' ' + s;
for (int i = 2, j = 0; i <= m; i++)
{
while (j && s[i] != s[j + 1]) j = ne[j];
if (s[i] == s[j + 1]) j++;
ne[i] = j;
}
dp[0][0]=1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= m; j++)
{
for (char x = 'a'; x <= 'z'; x++)//枚举第i+1位字母是x
{
int k = j;
while (k && s[k + 1] != x) k = ne[k];
if (s[k + 1] == x) k++;
if (k < m) dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % mod;//没有完全匹配子串
}
}
}
int ans = 0;
for (int i = 0; i < m; i++) ans = (ans + dp[n][i]) % mod;
cout << ans;
}