Acwing 1057. stock trading IV

Topic link
The question ： I'll tell you that the stock price doesn't exceed k The largest profit obtained by the secondary exchange
Answer key ：dp State machine model
This question can be divided into many states ：
1： It can be divided into pairs i Zhang stock operates and does not operate , So our state representation is correct , But we can't find the last status to update this status , Because the previous state can be operated or not , If the state representation is described like this , It is impossible to continue the following operations .
2： It can be divided into three states , Right. i Buy stocks , sell , Do not operate . We found that , The current trading of stocks has nothing to do with the trading of stocks at the upper level .
Think of this , We can find out , It is not possible to analyze a single stock , So it needs to be analyzed as a whole .
So we can decompose the state into traversal to the i When you buy stocks , No stock in hand and stock in hand . In this way, we will not only analyze this stock , Each state is related to the whole . Those who have stocks in their hands can have stocks in the previous state, with or without stocks , When there is no stock in hand, you can have the last one with or without stock . The specific state calculation and analysis is very simple .
We put dp[i][j][0] Treat as in front i The choice is , Working on the second j operations , The biggest profit without stocks .
dp[i][j][1] Treat as in front i The choice is , Working on the second j operations , The biggest profit from holding stocks .
So we can analyze ;
dp[i][j][0]=max(dp[i-1][j][1]+a[i],dp[i-1][j][0]);
The above values respectively mean that there are goods in the upper half of the state, but these half of the state are sold , And the upper half of the state is already out of stock
dp[i][j][1]=max(dp[i-1][j-1][0]-a[i],dp[i-1][j][1]);
This update is slightly different , Because if there are goods at this time, the last state must have ended , So it is dp[i-1][j-1][0], And then there was dp[i-1][j][1], Indicates that the upper half of the status is available .
Here is AC Code ：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+7;
int a[N];
int dp[N][110][2];
signed main()
{
    
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(dp,-0x3f,sizeof(dp));// This initialization is very important , Because there may be negative numbers in the process 
    for(int i=0;i<=n;i++) dp[i][0][0]=0;// from 0 Start , Because in the early stage dp It is necessary to use dp[0][0][0] Of 
    for(int i=1;i<=n;i++)
    {
    
        for(int j=1;j<=k;j++)
        {
    
            dp[i][j][0]=max(dp[i-1][j][1]+a[i],dp[i-1][j][0]);
            dp[i][j][1]=max(dp[i-1][j-1][0]-a[i],dp[i-1][j][1]);
        }
    }
    int ans=0;
    for(int i=1;i<=k;i++)
    {
    
        ans=max(dp[n][i][0],ans);// This must be dp[n][i][0], Because the final state must be that there is no stock in hand .
    }
    printf("%d\n",ans);
    return 0;
}

summary ：dp The explanation of the state is very important , The same dp Array , about dp Different interpretations of arrays have different approaches , There are different transfer equations , So do dp Be sure to be clear about the state , In this way, we can make a good analysis .