广州建设厅网站首页/网址导航哪个好

股票买卖 1

原题链接

这道题就是求max {ai−aj|j<i}

#include<iostream>using namespace std;const int N = 1e5+10;int a[N];
int n;
int mi = 0x3f3f3f3f;
int ans = 0;int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];mi = min(a[i],mi);if(i!=1){ans = max(ans,a[i]-mi);}}cout << ans;return 0;
}

股票买卖 2

原题链接

#include<iostream>using namespace std;const int N = 1e5+10;int a[N];int n;int main()
{cin >> n;int ans = 0;for(int i = 1; i <= n; i++){cin >> a[i];if(i!=1)ans = ans + max(0,a[i]-a[i-1]);}cout << ans;return 0;
}

股票买卖 3

方法一：前后缀拆分dp

怎么想到的？

首先我们想的是，先按着第一道题的方法，遍历一边数组，得到买卖一次的最大值，然后再遍历一次，得到买卖第二次的最大值，但是这个是不行的。
原因是，这道题要求我们，第二次买之前，第一次的必须卖出去

所以，我们想到的是开两个dp数组

#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;
int arr[N];int dp[N];
int rdp[N];int n;int main()
{cin >> n;for (int i = 0; i < n; i++) {cin >> arr[i];}int low = 9999999;int ans = 0;for (int i = 0; i < n; i++) {low = min(low, arr[i]);ans = max(ans, arr[i] - low);dp[i] = ans;}int high = 0;ans = 0;for (int i = n - 1; i >= 0; i--) {high = max(high, arr[i]);ans = max(ans, high - arr[i]);rdp[i] = ans;}ans = 0;for (int i = 0; i < n; i++) {ans = max(ans,dp[i] + rdp[i]);}cout << ans << endl;return 0;
}

方法二：状态机dp

f[0/1][i]表示只考虑前i支股票且手头有/没有股票的最大收益

#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
#define MAXN 200011
ll f[5][MAXN];
int main()
{memset(f,0xcf,sizeof f);ll n;scanf("%lld",&n);f[0][0]=0;for(ll i=1;i<=n;++i){ll x;scanf("%lld",&x);f[0][i]=f[0][i-1];f[1][i]=std::max(f[1][i-1],f[0][i-1]-x);f[2][i]=std::max(f[2][i-1],f[1][i-1]+x);f[3][i]=std::max(f[3][i-1],f[2][i-1]-x);f[4][i]=std::max(f[4][i-1],f[3][i-1]+x);}printf("%lld",std::max(f[0][n],std::max(f[2][n],f[4][n])));return 0;
}

股票买卖 4

原题链接

考虑前 i 天的股票，第 i 天的 决策 是 k，且完成的 完整交易数 为 j 的方案

#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; //初始状态f[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][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 j = 0; j <= k; ++ j) res = max(res, f[n][j][0]); //目标状态f[n][j][0]cout << res << endl;return 0;
}

#include <iostream>
#include <cstring>using namespace std;const int N = 1e5 + 10, M = 110;int n, k;
int w[N];
int f[2][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; //初始状态f[0][0][0]for (int i = 1; i <= n; ++ i){for (int j = 0; j <= k; ++ j){f[i & 1][j][0] = f[(i - 1) & 1][j][0];if (j) f[i & 1][j][0] = max(f[i & 1][j][0], f[(i - 1) & 1][j - 1][1] + w[i]);f[i & 1][j][1] = max(f[(i - 1) & 1][j][1], f[(i - 1) & 1][j][0] - w[i]);}}int res = 0;for (int j = 0; j <= k; ++ j) res = max(res, f[n & 1][j][0]); //目标状态f[n][j][0]cout << res << endl;return 0;
}

股票买卖 5

#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; //初始状态f[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][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 j = 0; j <= k; ++ j) res = max(res, f[n][j][0]); //目标状态f[n][j][0]cout << res << endl;return 0;
}

#include <iostream>
#include <cstring>using namespace std;const int N = 1e5 + 10, M = 110;int n, k;
int w[N];
int f[2][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; //初始状态f[0][0][0]for (int i = 1; i <= n; ++ i){for (int j = 0; j <= k; ++ j){f[i & 1][j][0] = f[(i - 1) & 1][j][0];if (j) f[i & 1][j][0] = max(f[i & 1][j][0], f[(i - 1) & 1][j - 1][1] + w[i]);f[i & 1][j][1] = max(f[(i - 1) & 1][j][1], f[(i - 1) & 1][j][0] - w[i]);}}int res = 0;for (int j = 0; j <= k; ++ j) res = max(res, f[n & 1][j][0]); //目标状态f[n][j][0]cout << res << endl;return 0;
}作者：一只野生彩色铅笔
链接：https://www.acwing.com/solution/content/55037/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

股票买卖 6

原题链接

#include <iostream>const int N=100010;int n,f;
int data[N];
int dp[2][N];int main()
{scanf("%d %d\n",&n,&f);for(int i=1;i<=n;i++)scanf("%d",&data[i]);dp[1][1]=-data[1];for(int i=2;i<=n;i++){dp[0][i]=std::max(dp[0][i-1],data[i]+dp[1][i-1]-f);dp[1][i]=std::max(dp[1][i-1],dp[0][i-1]-data[i]);}std::cout<<dp[0][n];return 0;
}