股票买卖 II

题意：给定股票每天的价格a[]，要求计算可以获得的最大利润（交易次数不限，只能买一股）

思考：贪心。若最优解有在第i天买，第j天卖，那么利润等同于连续在i...j 天买卖。所以只要a[i-1]<a[i]，就把它算到利润中去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
int n,a[100010];
LL ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(i!=1&&a[i]>a[i-1]) ans+=a[i]-a[i-1];
    }
    cout<<ans;
    return 0;
}

股票买卖 III

题意：在股票买卖 II上加限制：只能交易两次。

思考：dp。

状态：

f[0][i]:从来没有买过股票的最大收益
f[1][i]:第一次买股票的最大收益
f[2][i]:卖掉一次股票的最大收益
f[3][i]:卖掉一次股票，又买了一次的最大收益
f[4][i]:卖掉两次股票的最大收益

转移：简单的状态机模型，不动/买/卖，见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
LL n,f[100010];
LL ans;
int main(){
   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]=max(f[1][i-1],f[0][i-1]-x);
        f[2][i]=max(f[2][i-1],f[1][i-1]+x);
        f[3][i]=max(f[3][i-1],f[2][i-1]-x);
        f[4][i]=max(f[4][i-1],f[3][i-1]+x);
    }
    printf("%lld",max(f[0][n],max(f[2][n],f[4][n])));
    return 0;
}

股票买卖 IV

题意：在股票买卖 II上加限制：只能交易k次。

思考：dp。

状态：f[i][j][k]:考虑前i天，交易了j次，现在手中是否有股票。

转移：简单的状态机模型，不动/买/卖，见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e2 + 10;
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;
}

股票买卖 V

题意：在股票买卖 II上加限制：卖出股票后，你无法在第二天买入股票 (即冷冻期为 11 天)。

思考：dp。

状态表示f[i][j]前i天，(j=0) 当前没有股票，(j=1) 当前有股票 ，(j=2) 当前没有股票，且处于冷冻期 （冷冻期）

状态机：

优化：滚动数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int w[N];
int f[2][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 & 1][0] = max(f[(i - 1) & 1][0], f[(i - 1) & 1][2]);
        f[i & 1][1] = max(f[(i - 1) & 1][1], f[(i - 1) & 1][0] - w[i]);
        f[i & 1][2] = f[(i - 1) & 1][1] + w[i];
    }
    cout << max(f[n & 1][0], f[n & 1][2]) << endl;
    return 0;
}