4 状态机

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int f[N][2];
int main()
{
   int t;
   cin>>t;
   while(t--)
   {
       int n;
       cin>>n;
       memset(f,0,sizeof f);//清空上一维状态
       f[0][0]=0,f[0][1]=-0x3f3f3f3f;//前0个不抢的状态是0，抢的话不可能所以定义负无穷
       for(int i=1;i<=n;i++)
       {
           int a;
           cin>>a;
           f[i][0]=max(f[i-1][0],f[i-1][1]);//不抢
           f[i][1]=f[i-1][0]+a;//抢
       }
       cout<<max(f[n][0],f[n][1])<<endl;//输出抢或不抢的最大值
   }
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=110;
int f[N][M][2],w[N];
int main()
{
  int n,k;
  cin>>n>>k;
  for(int i=1;i<=n;i++) cin>>w[i];
  memset(f,-0x3f,sizeof f);
  for(int i=0;i<=n;i++) f[i][0][0]=0;//表示前i天交易0次手里没股票是合法的方案
  for(int i=1;i<=n;i++)
    for(int j=1;j<=k;j++)
    {
       f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i]);
       f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);
    }
  int ans=0;
  for(int i=1;i<=k;i++) ans=max(ans,f[n][i][0]);//最后求一次前i天交易i次手里没股票的最大值
  cout<<ans<<endl;
   return 0;
}
/*滚动数组优化
#include<bits/stdc++.h>
using namespace std;
const int M=110;
int f[M][2];
int main()
{
  int n,k;
  cin>>n>>k;
  memset(f,-0x3f,sizeof f);
  f[0][0]=0;
  for(int i=1;i<=n;i++)
    {
        int w;
        cin>>w;
        for(int j=1;j<=k;j++)
       {
          f[j][0]=max(f[j][0],f[j][1]+w);
          f[j][1]=max(f[j][1],f[j-1][0]-w);
       }
    }
  int ans=0;
  for(int i=1;i<=k;i++) ans=max(ans,f[i][0]);
  cout<<ans<<endl;
   return 0;
}
*/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        auto &w=prices;//引用操作，也就是多一个名字
        int n=w.size(),f[5001][3];
        memset(f,-0x3f,sizeof f);
        f[0][2]=0;//因为入口相当于是前0天，手里没股票的2天
         for(int i=1;i<=n;i++)
         {
               f[i][0]=max(f[i-1][0],f[i-1][2]-w[i-1]);//手里有股票
               f[i][1]=f[i-1][0]+w[i-1];//手里没股票第一天
               f[i][2]=max(f[i-1][2],f[i-1][1]);//手里没股票大于1天
         }
         return max(f[n][1],f[n][2]);//最后求一次没股票的时候的最大价值
    }
};
/*滚动数组优化
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int f[3];
        f[0]=f[1]=-0x3f3f3f3f,f[2]=0;
         for(int i=0;i<prices.size();i++)
         {
             int temp0=f[0],temp1=f[1];
               f[0]=max(f[0],f[2]-prices[i]);
               f[1]=temp0+prices[i];
               f[2]=max(f[2],temp1);
         }
         return max(f[1],f[2]);
    }
};
*/