算法提高之股票买卖 IV

本文主要是介绍算法提高之股票买卖 IV，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法提高之股票买卖 IV

• 核心思想：状态机

  • 状态表示f[i,j,k]：考虑前 i 天的股票，第 i 天的 决策 是 k，且完成的 完整交易数 为 j 的方案
  • **状态计算：f[i,j,0]=max(f[i−1,j,0],f[i−1,j−1,1]+wi) **
    • f[i,j,1]=max(f[i−1,j,1],f[i−1,j,0]−wi)

•   #include <iostream>#include <cstring>using namespace std;const int N = 1e5 + 10, M = 110;int n, k;int w[N];int f[N][M][2]; int main(){cin>>n>>k;for(int i=1;i<=n;i++) cin>>w[i];memset(f,-0x3f,sizeof f);  //初始化f[0][0][0] = 0;for(int i=1;i<=n;i++){for(int j=0;j<=k;j++){f[i][j][0] = f[i-1][j][0];if(j) f[i][j][0] = max(f[i-1][j][0],f[i-1][j-1][1]+w[i]);f[i][j][1] = max(f[i-1][j][1],f[i-1][j][0] - w[i]);}}int res=0;for(int i=1;i<=k;i++) res = max(res,f[n][i][0]);cout<<res<<endl;return 0;}
  

这篇关于算法提高之股票买卖 IV的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---