NO.83十六届蓝桥杯备战|动态规划-基础线性DP|台阶问题|最大子段和|传球游戏|乌龟棋(C++)

线性dp是动态规划问题中最基础、最常⻅的⼀类问题。它的特点是状态转移只依赖于前⼀个或前⼏个状态，状态之间的关系是线性的，通常可以⽤⼀维或者⼆维数组来存储状态

P1192 台阶问题 - 洛谷

斐波那契数列模型

1. 状态表⽰：
   dp[i] 表⽰：⾛到i 位置的⽅案数。
   那么dp[n] 就是我们要的结果。
2. 状态转移⽅程：
   可以从$i-k\le j\le i-1$区间内的台阶⾛到i位置，那么总⽅案数就是所有的dp[j]累加在⼀
   起。
   注意i - k 不能⼩于0 。
3. 初始化：
   dp[0] = 1 ，起始位置，为了让后续填表有意义。
4. 填表顺序：
   从左往右

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, MOD = 1e5 + 3;

int n, k;
int f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;

    f[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k && i-j >= 0; j++)
        {
            f[i] = (f[i] + f[i-j]) % MOD;        
        }
    }
    cout << f[n] << endl;
    
    return 0;
}

P1115 最大子段和 - 洛谷

1. 状态表⽰：
   dp[i] 表⽰：以i 位置元素为结尾的「所有⼦数组」中和的最⼤值。
   那我们的最终结果应该是dp 表⾥⾯的最⼤值。
2. 状态转移⽅程：
   dp[i] 的所有可能可以分为以下两种：
   a. ⼦数组的⻓度为1 ：此时dp[i] = a[i] ；
   b. ⼦数组的⻓度⼤于1 ：此时dp[i]应该等于以i-1为结尾的「所有⼦数组」中和的最⼤值再
   加上a[i] ，也就是dp[i - 1] + a[i] 。
   应该是两种情况下的最⼤值，因此可得转移⽅程：dp[i] = max(a[i], dp[i - 1] + a[i]) 。
3. 初始化：
   把第⼀个格⼦初始化为0 ，往后填数的时候就不会影响最终结果。
4. 填表顺序：
   根据「状态转移⽅程」易得，填表顺序为「从左往右」

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n;
int f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    int ret = -1e9;
    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x;

        f[i] = max(f[i-1] + x, x);
        ret = max(ret, f[i]);
    }
    cout << ret << endl;
    
    return 0;
}

P1057 [NOIP 2008 普及组] 传球游戏 - 洛谷

1. 状态表⽰：
   f[i][j] 表⽰传了i 次，落在第j 个⼈⼿⾥时的总⽅案数。
   那么f[m][1] 就是我们想要的结果。
2. 状态转移⽅程：
   因为是⼀个环形结构，第⼀个位置和最后⼀个位置可以特殊处理：
   a. 当$2\le j\le n-1$时，可以从$j-1$或者$j+1$传到该位置，那么总⽅案数就是$f[i-1][j-1]+f[i-1][j+1]$ ；
   b. 当j = 1 时，可以从n 或者2 传到该位置，那么总⽅案数就是f[i - 1][n] + f[i - 1][2]
   c. 当j = n 时，可以从$n-1$或者$1$传到该位置，那么总⽅案数就是$f[i-1][1]+f[i-1][n-1]$
3. 初始化：
   刚开始的状态设置为1 ，让后续填表是正确的，f[0][1] = 1 。
4. 填表顺序：
   ⼀定要先循环次数，再循环位置。因为我们更新状态是从低次数更新⾼次数，也就是第⼀⾏更新第⼆⾏。因此填表顺序应该是从上往下每⼀⾏，⾏的顺序⽆所谓

#include <bits/stdc++.h>
using namespace std;

const int N = 50;

int n, m;
int f[N][N]; //f[i][j]表示传递了i次之后落在了j号同学手里的方案数

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    f[0][1] = 1;
    for (int i = 1; i <= m; i++)
    {
        //第一个人
        f[i][1] = f[i-1][2] + f[i-1][n];
        //中间的人
        for (int j = 2; j < n; j++)
        {
            f[i][j] = f[i-1][j-1] + f[i-1][j+1];        
        }
        //第n个人
        f[i][n] = f[i-1][1] + f[i-1][n-1];
    }
    cout << f[m][1] << endl;
    
    return 0;
}

P1541 [NOIP 2010 提高组] 乌龟棋 - 洛谷

1. 状态表⽰
   f[i][a][b][c][d]表⽰：⾛到i位置时，编号为1234的卡⽚分别⽤了abcd张，此时的最⼤分
   数。
   我们发现，当1234⽤的卡⽚数确定之后，⾛到的位置i可以计算出来，其中
   i = 1 + a + 2b + 3c + 4d
   因此状态表⽰可以优化掉⼀维，变成f[a][b][c][d]，表⽰：编号为1234的卡⽚分别⽤了abcd张，此时的最⼤分数。
2. 状态转移⽅程：
   设根据最后⼀次⽤的卡⽚种类，分情况讨论：
   a. 如果a > 0 ，并且最后⼀张⽤1 卡⽚，最⼤分数为： f[a - 1][b][c][d] + nums[i] ；
   b. 如果b > 0 ，并且最后⼀张⽤2 卡⽚，最⼤分数为：f[a][b - 1][c][d] + nums[i] ；
   c. 如果c > 0 ，并且最后⼀张⽤3 卡⽚，最⼤分数为：f[a][b][c - 1][d] + nums[i] ；
   d. 如果d > 0 ，并且最后⼀张⽤4 卡⽚，最⼤分数为：f[a][b][c][d - 1] + nums[i] ；
   综上所述，取四种情况⾥⾯的最⼤值即可。
3. 初始化：
   ⼀张卡⽚也不⽤的情况下，可以获得第⼀个格⼦的分数，f[0][0][0][0] = nums[1] 。
4. 填表顺序：
   从⼩到⼤枚举每种卡⽚使⽤的张数即可

#include <bits/stdc++.h>
using namespace std;

const int N = 360, M = 50;

int n, m;
int x[N], cnt[5];
int f[M][M][M][M];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i];

    for (int i = 1; i <= m; i++)
    {
        int t; cin >> t;
        cnt[t]++;
    }

    //初始化
    f[0][0][0][0] = x[1];
    for (int a = 0; a <= cnt[1]; a++)
        for (int b = 0; b <= cnt[2]; b++)
            for (int c = 0; c <= cnt[3]; c++)
                for (int d = 0; d <= cnt[4]; d++)
                {
                    int i = 1 + a + 2 * b + 3 * c + 4 * d;
                    int& t = f[a][b][c][d];
                    if (a) t = max(t, f[a-1][b][c][d] + x[i]);
                    if (b) t = max(t, f[a][b-1][c][d] + x[i]);
                    if (c) t = max(t, f[a][b][c-1][d] + x[i]);
                    if (d) t = max(t, f[a][b][c][d-1] + x[i]);
                }
    cout << f[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;
        
    return 0;
}