股票问题汇总

股票问题，指给定一系列数列，可以在某些天以当天价格买入，也可以在某些天以当天价格卖出。

按照买卖规则，可以分为：
1. 不能进行多笔交易；买股票之前只能先把手上的股票卖出。一般此类题是dp。
2. 可以进行多笔交易；手里可以同时持有多只股票。一般要贪心。

股票问题的核心是发现如何使得手里的资产最多。

无论是哪种模型，都可以看成如果第二天价格更高就卖，大不了可以反悔（可以以这天的价格再把卖掉的股票再买回来）。

问题1

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
int w[maxn], f[maxn][110][2];
int main()
{
    int n, k; scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    memset(f, 0xcf, sizeof f);
    for(int i = 0; i <= n; 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] + w[i], f[i - 1][j][0]);
            f[i][j][1] = max(f[i - 1][j - 1][0] - w[i], f[i - 1][j][1]);
        }
    }
    int ans = 0;
    for(int i = 0; i <= k; i++) ans = max(ans, f[n][i][0]);
    cout << ans << endl;

}

问题2

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
int w[maxn], f[maxn][3];
int main()
{
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    memset(f, 0, sizeof f);
    f[0][1] = f[0][2] = -0x3f3f3f;
    for(int i = 1; i <= n; i++)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][1]);
        f[i][1] = f[i - 1][2] + w[i];
        f[i][2] = max(f[i - 1][0] - w[i], f[i - 1][2]);
    }
    cout << max(f[n][1], max(f[n][0], f[n][2])) << endl;
}

问题3

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 233;
int a[110][110], w[110][110];
int f[maxn];
int main()
{
    int T, n, m;
    scanf("%d%d%d", &T, &n, &m);
    for(int i = 1; i <= T; i++)
        for(int j = 1; j <= n; j++) scanf("%d", &a[i][j]), w[i][j] = a[i][j] - a[i - 1][j];

    for(int i = 1; i < T; i++)
    {
        memset(f, 0, sizeof f);
        int tm = m;
        for(int j = 1; j <= n; j++)
        {
            for(int k = a[i][j]; k <= m; k++)
            {
                f[k] = max(f[k], f[k - a[i][j]] + w[i + 1][j]);
                tm = max(tm, f[k] + k);
            }
        }
        m = tm;
        //cerr << m << endl;
    }
    printf("%d\n", m);
}

问题4

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector> 
#include<utility>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > b;

ll n,t;
ll ans = 0;
int main()
{
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &t);
        b.push(t);
        if(b.top() < t)
        {
            ans += t - b.top();
            b.pop();
            b.push(t);
        }
    }
    printf("%lld", ans);
}