【状态机模型】大盗阿福 买卖股票IV V

一、大盗阿福


1049. 大盗阿福 - AcWing题库

题意：

 思路：

简单的状态机模型，其实就是树形dp没有上司的舞会的线性版本

状态设计：

给第i个位置的dfs状态分个类：

设dp[i][0]为：到达第i个位置并不选这个位置的所有路径中所能拿到的最大利益

dp[i][1]为：到达第i个位置并选这个位置的所有路径中所能拿到的最大利益

设计完状态，发现这两个状态覆盖了所有情况，不重不漏，且对于设计的每个状态都是确定的，因此该状态设计合理

状态转移：

对于dp[i][0]：考虑决策：只有一个，不选，那么第i-1个决策可以是被选的状态，也可以是没被选的状态

dp[i][0]=max(dp[i-1][0],dp[i-1][1]);

对于dp[i][1]：考虑决策：只有一个，选，那么第i-1个决策一定是没被选上的状态

dp[i][1]=dp[i-1][0]+a[i];

初始化：

因为属性是求最大值，因此初始化为inf，且dp[0][0]=0

Code：

#include 
using namespace std;
const int mxn=1e5+10,inf=0xc0c0c0c0;
int n;
int a[mxn],dp[mxn][2];
void solve(){
    memset(dp,inf,sizeof(dp));
    dp[0][0]=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-1][0]+a[i];
    }
    cout<<max(dp[n][0],dp[n][1])<<'\n';
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

二、股票买卖IV

1057. 股票买卖 IV - AcWing题库

题意：

思路：

状态设计：

在状态设计的时候，也可以考虑决策能转移到哪种状态，来对dfs状态进行分类

对于第i天，状态可以分类为：已经买了j个股票，是买入/卖出状态

设dp[i][j][0]为到达第i天，已经买了j个股票，是卖出状态

dp[i][j][1]为到达第i天，已经买了j个股票，是买入状态

状态转移：

考虑决策：买or不买

对于买的决策：前一个状态一定为卖出状态

对于卖的决策，前一个状态一定为买入状态

#include 
using namespace std;
const int mxn=1e5+10,inf=0xc0c0c0c0;
int n,k;
int a[mxn],dp[mxn][110][2];
int main(){
    memset(dp,inf,sizeof(dp));
    dp[0][0][0]=0;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j][0]=dp[i-1][j][0];
            dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j][0]-a[i]);
            if(j>0) dp[i][j][0]=max(dp[i-1][j-1][1]+a[i],dp[i-1][j][0]);
        }
    }
    int ans=inf;
    for(int j=0;j<=k;j++) ans=max(ans,max(dp[n][j][0],dp[n][j][1]));
    printf("%d\n",ans);
    return 0;
}

这里注意，若j<=0，那么至少要保证dp[i-1][j][0]要转移到dp[i][j][0]，因此要先转移好

三、股票买卖V

1058. 股票买卖 V - AcWing题库

思路：

状态设计：

在设计状态时，可以看看决策，来对dfs状态进行分类

我们发现，如果买了之后，就是持股状态

卖出之后，就是冷冻状态

再过一天，就是空股状态

设dp[i][0]为到第i天的空股状态

dp[i][1]为到第i天的持股状态

dp[i][2]为到第i天的冷冻期

这三个状态不重不漏，是合理的

如果看两个dfs状态是否一样，就看它们的决策是否一样就行

状态转移：

对于dp[i][0]：决策只能是冷冻和不变

如果是冷冻，那就是从dp[i-1][2]转移过来

如果是不变，那就是从dp[i-1][0]转移过来

对于dp[i][1]：决策只能是买入或不变

如果是买入，那就是从dpi-1][0]转移过来

如果是不变，那就是从dp[i-1][1]转移过来

对于dp[i][2]，决策只能是卖出

因此只能从dp[i-1][1]转移过来

初始化：因为是求最大值，因此全部初始化成最小值就行，然后dp[0][0]=0

Code：

//判断两个(dfs)状态是否一样，看它们接下来的决策是否是一样的
//考虑状态转移时，考虑图论：前一个结点+前一个结点的决策，当前的状态是前一个的状态经过有向边（决策）转移过来的，这样不会想错
#include 
using namespace std;
const int mxn=1e5+10,inf=0xc0c0c0c0;
int n;
int a[mxn],dp[mxn][3];
int main(){
    memset(dp,inf,sizeof(dp));
    dp[0][0]=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][2]);
        dp[i][1]=max(dp[i-1][0]-a[i],dp[i-1][1]);
        dp[i][2]=dp[i-1][1]+a[i];
    }
    printf("%d\n",max(dp[n][0],max(dp[n][1],dp[n][2])));
    return 0;
}

滚动数组优化：

//判断两个(dfs)状态是否一样，看它们接下来的决策是否是一样的
//考虑状态转移时，考虑图论：前一个结点+前一个结点的决策，当前的状态是前一个的状态经过有向边（决策）转移过来的
//滚动数组
#include 
using namespace std;
const int mxn=1e5+10,inf=0xc0c0c0c0;
int n;
int a[mxn],dp[3],dp2[3];
int main(){
    memset(dp,inf,sizeof(dp));
    dp[0]=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        memcpy(dp2,dp,sizeof(dp));
        dp[0]=max(dp2[0],dp2[2]);
        dp[1]=max(dp2[0]-a[i],dp2[1]);
        dp[2]=dp2[1]+a[i];
    }
    printf("%d\n",max(dp[0],max(dp[1],dp[2])));
    return 0;
}