将决策的过程等效为各个状态的转移

大盗阿福

状态:考虑第$i$个物品

1. 不拿

2. 拿

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

using namespace std;

const int N = 100010;

int T, n;
int w[N], f[N][2];

int main()
{
    cin >> T;
    while (T --)
    {
        cin >> n;
        for (int i = 1; i <= n; i ++)
            scanf ("%d", &w[i]);

        for (int i = 1; i <= n; i ++)
        {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            // 如果不拿第i个物品, 那可以从不拿i - 1个和拿第i - 1个物品转移过来
            f[i][1] = f[i - 1][0] + w[i];
            // 如果拿第i个物品, 那就只能从不拿第i - 1个物品转移过来
        }

        printf ("%d\n", max(f[n][0], f[n][1]));
    }
    return 0;
}

股票买卖 IV

状态: 在考虑第$i$件物品时

1. 手中有货

2. 手中无货

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

using namespace std;

const int N = 100010, M = 110;

int n, m;
int w[N];
int f[N][M][2];

int main()
{
    scanf ("%d %d", &n, &m);

    for (int i = 1; i <= n; i ++) scanf ("%d", &w[i]);

    memset(f, -0x3f, 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 <= m; j ++)
        {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            // 1.由无货转移而来   2.由有货转移而来, 卖掉的价值为w[i]
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
            // 1.由有货转移而来   2.由无货转移而来, 买的消耗为w[i]
        }

    int res = 0;
    for (int i = 0; i <= m; i ++) res = max(res, f[n][i][0]);

    printf ("%d", res);
    return 0;
}

股票买卖 V

状态: 在考虑第$i$件物品时

1. 手中有货

2. 卖出第一天

3. 卖出两天及以上

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

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

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

int main()
{
    scanf ("%d", &n);

    for (int i = 1; i <= n; i ++) scanf ("%d", &w[i]);

    f[0][0] = f[0][1] = -INF;
    f[0][2] = 0;

    for (int i = 1; i <= n; i ++)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
        // 1. 由手中有货转移而来    2.由卖出两天及以上转移而俩, 则买入的消费为w[i]
        f[i][1] = f[i - 1][0] + w[i];
        // 1. 只能用手中有货转移而来, 收益为w[i]
        f[i][2] = max(f[i - 1][2], f[i - 1][1]);
        // 1. 由卖出第一天转移而来  2. 由卖出两天以上转移而来
    }

    printf ("%d", max(f[n][1], f[n][2]));
    return 0;
}

设计密码

状态: 在考虑模板串第$i$位时, 有26种不同的情况

大佬题解