笔记汇总

线性DP

P1

数据量不大，考虑暴力储存。

设 $f(a, b, c, d, e)$ 为每排人数为 $a, b, c, d, e$ 的方案；

由于核心性质：

从高到低依次安排每个同学的位置，那么在安排过程中，当前同学一定占据每排最靠左的连续若干个位置，且从后往前每排人数单调递减。否则一定不满足“每排从左到右身高递减，从后到前身高也递减”这个要求。

得出代码：

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

const int N = 31;

typedef long long LL;

int k;
int s[N];
LL f[N][N][N][N][N];

int main()
{
    while (scanf("%d", &k) && k != 0)
    {
        memset(s, 0, sizeof s);
        memset(f, 0, sizeof f);
        for (int i = 0; i < k; i ++ ) scanf("%d", &s[i]);

        f[0][0][0][0][0] = 1;
        for (int a = 0; a <= s[0]; a ++ )
            for (int b = 0; b <= min(a, s[1]); b ++ )
                for (int c = 0; c <= min(b, s[2]); c ++ )
                    for (int d = 0; d <= min(c, s[3]); d ++ )
                        for (int e = 0; e <= min(d, s[4]); e ++ )
                        {
                            LL &x = f[a][b][c][d][e];
                            if (a > b) x += f[a-1][b][c][d][e];
                            if (b > c) x += f[a][b-1][c][d][e];
                            if (c > d) x += f[a][b][c-1][d][e];
                            if (d > e) x += f[a][b][c][d-1][e];
                            if (e) x += f[a][b][c][d][e-1];
                        }
        printf("%lld\n", f[s[0]][s[1]][s[2]][s[3]][s[4]]);
    }
}

P2

由于卡片有后效性，要作为状态储存。

空间炸掉，考虑简化状态：

发现玩家所处位置可以直接用卡片用了哪几张得到，

状态简化。

本题阶段，$1$ 卡用了多少，$2$ 卡用了多少…

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

const int N = 400, M = 41;

int n, m;
int w[N], b[N], R[5];
int f[M][M][M][M];

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

    f[0][0][0][0] = w[1];
    for (int a = 0; a <= R[1]; a ++ ) 
        for (int b = 0; b <= R[2]; b ++ ) 
            for (int c = 0; c <= R[3]; c ++ ) 
                for (int d = 0; d <= R[4]; d ++ ) 
                {
                    int W, A = 0, B = 0, C = 0, D = 0;
                    W = w[a + 2 * b + 3 * c + 4 * d + 1];
                    if (a >= 1) A = f[a - 1][b][c][d] + W;
                    if (b >= 1) B = f[a][b - 1][c][d] + W;
                    if (c >= 1) C = f[a][b][c - 1][d] + W;
                    if (d >= 1) D = f[a][b][c][d - 1] + W;
                    int L = max(A, B), R = max(C, D);
                    f[a][b][c][d] = max(f[a][b][c][d], max(L, R));
                }

    printf("%d", f[R[1]][R[2]][R[3]][R[4]]);

}

P3

表面上是一个背包$DP$，但是变化量太多，且需要保持顺序关系（由最后一步划分来看，就是确保前 $i-1$ 个酸奶都在前 $j-1$ 层，当然事实情况会在第 $i$ 个酸奶上复杂一些）

此时如果我们定义状态为：前$i$朵花里边选且，第$i$朵花放在第$j$个花瓶的最大值，

需要从前$j-1$个花盆中找到最大的，决策数为$n$，考虑如何优化，

因为转移有大量重复，将状态修改为前$j$个花盆，就可以由上层转移。

这启发我们，对于决策集合只增多不减少的情况，可以考虑修改状态由第几个至前几个。

当然，这类问题也可以用数据结构进行优化，本题就可以。

只有多用花，才会增加价值，列式后发现是数字三角形的变形题，虽然只有状态上可以这么看。

转移完路径回溯输出。

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

const int N = 1e3 + 10;

int n, m;
int a[N][N], f[N][N];

void dfs(int i, int j)
{
    if (i == 0 || j == 0) return;
    while (f[i][j] == f[i][j-1]) j --;
    dfs(i-1, j-1);
    printf("%d ", j);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= m; j ++ )
        {
            if (i == j) f[i][j] = f[i-1][j-1] + a[i][j];
            else f[i][j] = max(f[i][j-1], f[i-1][j-1] + a[i][j]);
        }
    printf("%d\n", f[n][m]);
    dfs(n, m);
}

本题所有花都必须插上去，且要保证顺序，所以 $i == j$ 时只能一一对应，

不然就看看是选择插入前面的瓶子还是插入最新的瓶子。

路径回溯时就往前面的瓶子搜，就可以保证字典序最小了。

如果不保证顺序，就是一个二分图最大带权匹配问题了。

P4

求最长上升子序列，及其方案数。

因为以同一元素为结尾的 $LDS$ 不一定只有一种，所以要多开个数组累计。

注意要求

如果两种方案的买入日序列不同，但是价格序列相同，则认为这是相同的方案

对于结尾元素相同，$LDS$ 序列长度相等的方案，将其中一个置为 $0$

本题数据过水，理应卡掉 $O(n^2logn)$ 和不在 $f[i]$ 计算完后判重的算法。

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

const int N = 5e3 + 10;

int n;
int a[N], f[N], g[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = g[i] = 1;
        for (int j = 1; j < i; j ++ )
        {
            if (a[i] < a[j])
            {
                if (f[i] < f[j] + 1)
                {
                    f[i] = f[j] + 1;
                    g[i] = g[j];
                }
                else if (f[i] == f[j] + 1)
                {
                    g[i] += g[j];
                }
            }
        }
        for (int j = 1; j < i; j ++ )
            if (a[i] == a[j] && f[i] == f[j]) g[j] = 0;
    }

    int ans = 0, num = 0;
    for (int i = 1; i <= n; i ++ ) 
        if (ans < f[i])
        {
            ans = f[i];
        }
    for (int i = 1; i <= n; i ++ )
        if (ans == f[i])
        {
            num += g[i];
        }
    printf("%d %d", ans, num);
}

P5

$LCS$ 变形题，为了储存具体方案，我们要在过程中储存路径的相关点，

由于路径上点的可能数集很小，所以我们暴力统计。

最后采用路径回溯的方式求具体方案，

我们发现，

当选择的字符一样时, 选择字符的位置越靠近$x,y$越优，

因为包含前面同样是相同字符时的情况，而且真实情况的限制更强，

也就是说只有最近的相同字符，才能增加最优解方案数。

所以直接找距离 $x$ 和 $y$ 最近的字符$a$的位置即可；

预处理所有字符的最近位置后，可以通过此题。

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

const int N = 85;

char a[N], b[N], res[N];
int f[N][N];
int fa[N][26], fb[N][26];
vector<string> ans;

void dfs(int x, int y, int k)
{
    if (!k) 
    {
        ans.push_back((string)(res + 1)); 
        return;
    }
    for (int i = 0; i < 26; i ++ )
    {
        int a = fa[x][i], b = fb[y][i];
        if (a < k || b < k || f[a][b] != k) continue;
        res[k] = 'a' + i;
        dfs(a-1, b-1, k-1);
    }
}

int main()
{
    scanf("%s%s", a + 1, b + 1);
    int n = strlen(a + 1), m = strlen(b + 1);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
        }
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < 26; j ++ )
        {
            if (a[i] - 'a' == j) fa[i][j] = i;
            else fa[i][j] = fa[i-1][j];
        }
    for (int i = 1; i <= m; i ++ )
        for (int j = 0; j < 26; j ++ )
        {
            if (b[i] - 'a' == j) fb[i][j] = i;
            else fb[i][j] = fb[i-1][j];
        }
    dfs(n, m, f[n][m]);
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i ++ )
        cout << ans[i] << endl;
}

P6

减操作，等价于将二号以后的数任意决定符号，来构造最终答案。

模拟题目，并用现有知识去套是一种很有效的思考方式，但不能拿来学知识，加油！

这里有一个新的$DP$设计思路，对于可以表示值域的值，我们定为状态，并对负数添上偏移量。

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

const int N = 1e2 + 5, del = 1e4;

int n, t, a[N];
int f[N][(del << 1) + 5], g[N][(del << 1) + 5], s[N];   // 数字前的符号

inline bool vaild(int x)
{
    return x >= -del && x <= del;
}

void dfs(int i, int j)  // 搜索路径
{
    if (i == 2)
    {
        s[1] = false;   // + s[1]
        s[2] = true;    // - s[2]
        return;
    }
    if (f[i][j + del]) s[i] = g[i][j+del]; // 找符号
    if (s[i]) dfs(i - 1, j + a[i]);
    else dfs(i - 1, j - a[i]);
}

int main()
{
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    f[2][a[1] - a[2] + del] = true;
    for (int i = 2; i < n; i ++ )  
        for (int j = -del; j <= del; j ++ )
        {
            if (f[i][j + del]) {
                if (vaild(j - a[i + 1]))
                {
                    f[i+1][j-a[i+1]+del] = true;
                    g[i+1][j-a[i+1]+del] = true;
                }
                if (vaild(j + a[i + 1]))
                {
                    f[i+1][j+a[i+1]+del] = true;
                    g[i+1][j+a[i+1]+del] = false;
                }
            }
        }
    dfs(n, t);
    int merged = 0; 
    for (int i = 2; i <= n; i ++ )  // 加号 = a - (b - c)
        if (!s[i]) printf("%d\n", i-1-merged), merged ++;   // 在新位置上
    for (int i = 2; i <= n; i ++ )
        if (s[i]) puts("1");    // 处理完符号就简单了
}

P7

可行性问题，有一个比最优化问题更快的解决方式。

我们发现，若前i种石头能凑出 sum/2，只有两种情况：
1. 在i阶段之前, 就已经$f[j]$ = true
2. 在i阶段之前, 就已经$f[j - i]$ = true

核心思想是在每一个$i$阶段都判断是否可以凑出下一个数，成立原因是交换律。

如果要求的是最优性，就是单调队列优化多重背包，观察代码发现，为了便于单调队列的转移，

我们将中间的循环拆成两部分，并用单调队列维护大小为$sv$的窗口在值域上滑动可转移到的最大值。

上文说的便于转移，是指，单调队列对于固定窗口大小（可以是值或下标范围）并有只同相对位置变化的变量（不包括常量），就可以转移。

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

int a[7], f[100005], used[200005];
int main()
{
    while (true)
    {
        a[0] = 0;
        for (int i = 1; i < 7; ++i) 
            cin >> a[i], a[0] += a[i] * i;
        if (a[0] == 0) break;
        if (a[0] & 1){puts("Can't"); continue; }
        memset(f, 0, sizeof f);
        a[0] >>= 1, f[0] = 1;
        for (int i = 1; i <= 6; i ++ )
        {
            memset(used, 0, sizeof used);
            for (int j = i; j <= a[0]; j ++ )
            {
                if (!f[j] && f[j-i] && used[j-i] < a[i])
                {
                    f[j] = 1;
                    used[j] = used[j-i] + 1;
                }
            }
        }
        if (!f[a[0]]) puts("Can't");
        else puts("Can");
    }
    return 0;
}

P8

P9

每个石子有两个参数，$(a,b),(b,c)$，因为涉及合并，我们分开存储。

所以状态表示是左端点左参数和右端点右参数，

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

const int N = 210;

int n;
int a[N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &a[i]), a[i + n] = a[i];    // 环拆链
    }

    for (int len = 3; len <= n + 1; len ++ )    // 至少要三个合并
        for (int l = 1, r; r = l + len - 1, r <= n << 1; l ++ ) // 最后记得要合并首尾
        {
            for (int k = l + 1; k < r; k ++ )   // 决策
            {
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
            }
        }

    int res = 0;
    for (int i = 1; i <= n; i ++ )  // 找最大值
    {
        int j = i + n;
        res = max(res, f[i][j]);
    }

    printf("%d", res);
}

P10

本题选择割掉的一块作下一次切割，但我们求的是总分，所以应该从小的考虑。

我们发现将一个大块划分成的每个小块都是相互独立的，且可以通过某些运算得到大块，

考虑区间$DP$和倍增$DP$，本题时限宽泛，用区间$DP$就可以了。

对于这种代码量很长的程序，一般会写记忆化搜索。

记得开$double$，

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

const int N = 16;

int n;
int s[N][N];
double f[N][N][N][N][N];
double X;

double get(int x1, int y1, int x2, int y2)  
{
    double delta = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    delta = delta - X;
    return delta * delta;
}

double dp(int k, int x1, int y1, int x2, int y2)
{
    if (f[k][x1][y1][x2][y2]) return f[k][x1][y1][x2][y2];
    if (k == n) return f[k][x1][y1][x2][y2] = get(x1, y1, x2, y2);

    double t = 1e9;
    for (int i = x1; i < x2; i ++ )
    {
        t = min(t, dp(k+1, x1, y1, i, y2) + get(i+1, y1, x2, y2));
        t = min(t, dp(k+1, i+1, y1, x2, y2) + get(x1, y1, i, y2));
    }
    for (int i = y1; i < y2; i ++ )
    {
        t = min(t, dp(k+1, x1, y1, x2, i) + get(x1, i+1, x2, y2));
        t = min(t, dp(k+1, x1, i+1, x2, y2) + get(x1, y1, x2, i));
    }
    return f[k][x1][y1][x2][y2] = t;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= 8; i ++ )
        for (int j = 1; j <= 8; j ++ )
            scanf("%d", &s[i][j]);

    for (int i = 1; i <= 8; i ++ )
        for (int j = 1; j <= 8; j ++ )
            s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];

    memset(f, 0, sizeof f);
    X = (double)s[8][8] / n;

    printf("%.3lf\n", sqrt(dp(1, 1, 1, 8, 8) / n));
}

P11

本题$DP$，难点在于同类项消除会有后效性，所以我们要多开一维限制，

我们采用增加状态定义$cnt$记录颜色与区间左右端点一样的方块数量，

这个方法正确，是因为它对不同同颜色方块在一起消除的可能性都统计到了。

需要注意的是，我们合并前一定消除了其它元素，所以最后一步是消除统计到的和左右端点颜色一样的方块，并计入贡献。

我们可以在读入时就将同色方块另作储存（初态要计算出值），减少状态数量，并在枚举$cnt$大小时，从左右端点已有的数量出发，然后可行性剪枝（确认上界），来高效运算。

我们只能从合法状态转移，这是因为不合法状态可能在区间第一次合并时错误转移过去，

当然求最大值初始化最小，并多考虑边界情况也是一种锻炼思维的方式。

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

const int N = 205;

int T, n, m, a[N], b[N];
int f[N][N][N];
int main()
{
    scanf("%d", &T);
    for (int C = 1; C <= T; C ++ )
    {
        scanf("%d", &n); m = 0;
        for (int i = 1; i <= n; i ++ )
        {
            int x;
            scanf("%d", &x);
            if (a[m] == x) b[m] ++;
            else a[ ++ m] = x, b[m] = 1;
        }
        memset(f, -0x3f, sizeof f);
        for (int i = 1; i <= m; i ++ ) f[i][i][0] = b[i] * b[i], f[i][i][b[i]] = 0;
        for (int len = 2; len <= m; len ++ )
            for (int l = 1; l + len - 1 <= m; l ++ )
            {
                int r = l + len - 1;
                for (int k = l; k < r; k ++ )
                {
                    f[l][r][0] = max(f[l][r][0], f[l][k][0] + f[k+1][r][0]);
                }
                if (a[l] != a[r]) continue;
                int tot = b[l] + b[r];
                for (int k = l + 1; k < r; k ++ )
                {
                    if (a[k] == a[l]) tot += b[k];
                }
                for (int cnt = b[l] + b[r]; cnt <= tot; cnt ++ )
                {
                    for (int k = l + 1; k <= r; k ++ )
                    {
                        if (a[l] == a[k])
                        {
                            f[l][r][cnt] = max(f[l][r][cnt], f[l+1][k-1][0] + f[k][r][cnt-b[l]]);
                        }
                    }
                    f[l][r][0] = max(f[l][r][0], f[l][r][cnt] + cnt * cnt);
                }
            }
        printf("Case %d: %d\n", C, f[1][m][0]);
    }
}

P12

本题子树互相独立，乘法原理计算方案数。

这是一道加深状态定义印象的好题，不同点也不一定包含最后一位元素，而是具体分析。

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

const int N = 310, mod = 1e9;

char a[N];
int f[N][N];
int main()
{
    scanf("%s", a + 1);
    int n = strlen(a + 1);
    for (int len = 1; len <= n; len += 2)   // 区间长度为奇数 ABA
    {
        for (int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;
            if (len == 1) f[l][r] = 1;  // 初始阶段
            else if (a[l] != a[r]) continue;
            for (int k = l; k < r - 1; k += 2)  // 合法状态必为奇数
            {
                if (a[k] != a[r]) continue;
                f[l][r] = (f[l][r] + f[l][k] * (long long)f[k+1][r-1]) % mod;
                // [l, k] 可能有多棵子树，[k+1, r-1] 只有一棵
                // 因为我们是找最后一个不同点，多棵子树可能会重复。
            }
        }
    }
    printf("%d", f[1][n]);
}