股票买卖 | CCBLOG

算法

关于二元一次方程的求解

ax + by = f, a + b = h; a, b是两个未知数，求解a, b的值。题目保证有整数解 。

可以先求出一个未知数b的值，可以推出b = (f - hx) / (y - x),在判断a + b == h ?

股票买卖I（简单贪心）

#include<iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int temp = 0x3f3f3f3f;
    int ans = 0;
    while(n --) {
        int x;
        cin >> x;
        ans = max(ans, x - temp);
        temp = min(temp, x);
    }
    cout << ans << endl;
    
    return 0;
}

股票买卖II（贪心）

贪心解法~

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n;
int a[N];
int f[N][2];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    
    int res = 0;
    for(int i = 2; i <= n; i ++) {
        res += max(0, a[i] - a[i - 1]);
    }
    cout << res << endl;
    return 0;
}

dp解法，f[i][0],f[i][1]分别表示第i天不持股和持股所获得的最大利润。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

int f[N][2];
int pr[N];

int main() {
    int n;
    cin >>  n;
    for(int i = 1; i <= n; i ++)
        cin >> pr[i];
    
    f[1][1] = -pr[1];
    
    for(int i = 2; i <= n; i ++) {
        f[i][0] = max(f[i - 1][0], f[i - 1][1] + pr[i]);
        f[i][1] = max(f[i - 1][0] - pr[i], f[i - 1][1]);
    }
    
    cout << max(f[n][0], f[n][1]) << endl;
    
    return 0;
}

max()函数比较多个数的大小

int maxn = max({a, b, c, d});注意a, b, c, d是同一个类型

股票买卖III

前后缀分解~

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

int p[N];
int dp1[N], dp2[N];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
        
    int t = 1e5;
    for(int i = 1; i <= n; i ++) {
        dp1[i] = max(dp1[i - 1], p[i] - t);
        t = min(t, p[i]);
    }
    
    t = -1;
    for(int i = n; i >= 1; i --) {
        t = max(t, p[i]);
        dp2[i] = ma'x(dp2[i + 1], t - p[i]);
    }
    
    int res = 0;
    for(int i = 1; i <= n; i ++)
        res = max(res, dp1[i] + dp2[i]);
        
    cout << res << endl;
    return 0;
}

股票IV

状态转移方程的初始化，非入口初始化为负无穷，入口按题目要求初始化。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010, M = 110;

int n, k;
int a[N];
int f[N][M][2];//f[i][j][k]表示的是第i天交易了j次，并且持股状态是k（0表示未持有，1表示持有）

int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    
    
    memset(f,0xcf,sizeof f);

    for(int i = 1; i <= n; i ++) {
        f[i][0][1] = max(f[i - 1][0][1], -a[i]);
        f[i][0][0] = 0;
    }
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= k; j ++) {
            f[i][j][0] = max(f[i - 1][j - 1][1] + a[i], f[i - 1][j][0]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] - a[i]);
        }
    
    int ans = 0;
    for(int i = 1; i <= k; i ++)
        ans = max(ans, f[n][i][0]);
        
    cout << ans << endl;
    return 0;
}

股票买卖V

有个一天的“冷静期”，即卖出要过一天才能买，不限次数，其余和股票IV一样。

f[i][0]表示的是第i天未持有股票，f[i][1]表示的是第i天持有股票，f[i][2]表示的是第i天刚买完，第i+1天处于“冷静期”，不能买股票。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int w[N];
int f[N][3];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> w[i];

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; ++ i)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][2]);
        f[i][1] = max(f[i - 1][1], f[i - 1][0] - w[i]);
        f[i][2] = f[i - 1][1] + w[i];
    }
    cout << max(f[n][0], f[n][2]) << endl;
    return 0;
}

股票买卖VI

和股票买卖II类似

#include<iostream>

using namespace std;

const int N = 100010;

int a[N];
int f[N][2];
int n, m;

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
        
    f[0][1] = -1e5;
    for(int i = 1; i <= n; i ++) {
        f[i][0] = max(f[i - 1][0], f[i - 1][1] + a[i] - m);
        f[i][1] = max(f[i - 1][0] - a[i], f[i - 1][1]);
    }

    cout << f[n][0] << endl;
    return 0;
}