# 股票问题汇总

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

#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;

}


#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;
}


#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);
}


#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);
}