👾线性动态规划

线性动态规划，即具有线性阶段划分的动态规划。

💭[P1216]数字三角形

[USACO1.5] [IOI1994]数字三角形 Number Triangles

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

img

在上面的样例中，从 $7 \to 3 \to 8 \to 7 \to 5$ 的路径产生了最大权值。

输入格式

第一个行一个正整数 $r$ ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

样例 #1

样例输入 #1

1
2
3
4
5
6

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出 #1

1

30

提示

【数据范围】
对于 $100%$ 的数据，$1\le r \le 1000$，所有输入在 $[0,100]$ 范围内。

题目翻译来自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1

🎈参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 120;
ll number[maxn][maxn];
ll dp[maxn][maxn]; // 记录走到(i,j)点时最好的和

int main() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= i;j++)
            cin >> number[i][j];
    for (int i = 1;i < n;i++)
        dp[n][i] = number[n][i];
    for (int i = n;i > 1;i--) {
        for (int j = 1;j <= i;j++) {
            dp[i - 1][j] = max(dp[i][j], dp[i][j + 1]) + number[i - 1][j];
        }
    }
    cout << dp[1][1] << endl;

    return 0;
}

💭[P1020]导弹拦截

[NOIP1999 普及组] 导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例 #1

样例输入 #1

1

389 207 155 300 299 170 158 65

样例输出 #1

1
2

6
2

提示

对于前 $50%$ 数据（NOIP 原题数据），满足导弹的个数不超过 $10^4$ 个。该部分数据总分共 $100$ 分。可使用$\mathcal O(n^2)$ 做法通过。
对于后 $50%$ 的数据，满足导弹的个数不超过 $10^5$ 个。该部分数据总分也为 $100$ 分。请使用 $\mathcal O(n\log n)$ 做法通过。

对于全部数据，满足导弹的高度为正整数，且不超过 $5\times 10^4$。

此外本题开启 spj，每点两问，按问给分。

$\text{upd 2022.8.24}$：新增加一组 Hack 数据。

🎈参考代码

 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
37
38
39

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 50;
vector<int>a, b, c;
int main() {
    int n;
    while (cin >> n) { a.push_back(n); }
    for (int i = 0;i < a.size();i++) {
        if (b.size() == 0 || a[i] <= b.back())
            b.push_back(a[i]);
        else {
            int l = 0, r = b.size() - 1;
            int pos = 0;
            while (l < r) {
                pos = (l + r) / 2;
                if (b[pos] >= a[i])l = pos + 1;
                else r = pos;
            }
            b[l] = a[i];
        }
        if (c.size() == 0 || c.back() < a[i])
            c.push_back(a[i]);
        else {
            int l = 0, r = c.size() - 1;
            int pos = 0;
            while (l < r) {
                pos = (l + r) / 2;
                if (c[pos] < a[i])l = pos + 1;
                else r = pos;
            }
            c[l] = a[i];
        }
    }
    cout << b.size() << endl;
    cout << c.size() << endl;

    return 0;
}

💭[P1091]合唱队形

[NOIP2004 提高组] 合唱队形

题目描述

$n$ 位同学站成一排，音乐老师要请其中的 $n-k$ 位同学出列，使得剩下的 $k$ 位同学排成合唱队形。

合唱队形是指这样的一种队形：设 $k$ 位同学从左到右依次编号为 $1,2,$ … $,k$，他们的身高分别为 $t_1,t_2,$ … $,t_k$，则他们的身高满足 $t_1< \cdots <t_i>t_{i+1}>$ … $>t_k(1\le i\le k)$。

你的任务是，已知所有 $n$ 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入格式

共二行。

第一行是一个整数 $n$（$2\le n\le100$），表示同学的总数。

第二行有 $n$ 个整数，用空格分隔，第 $i$ 个整数 $t_i$（$130\le t_i\le230$）是第 $i$ 位同学的身高（厘米）。

输出格式

一个整数，最少需要几位同学出列。

样例 #1

样例输入 #1

1
2

8
186 186 150 200 160 130 197 220

样例输出 #1

1

4

提示

对于 $50%$ 的数据，保证有 $n \le 20$。

对于全部的数据，保证有 $n \le 100$。

🎈参考代码

 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
37
38
39
40
41
42
43
44
45
46
47
48

void solve() {
    int n;cin >> n;
    vector<int>t;
    for (int i = 0; i < n; i++) {
        int x;cin >> x;
        t.push_back(x);
    }
    int k = 1;
    for (int m = 0;m < n;m++) {
        // 枚举中间位m
        vector<int>l, r;
        // 左边最长上升子序列
        for (int i = 0;i < m;i++) {
            if (t[i] >= t[m])continue;
            if (l.size()!=0) {
                if (t[i] > l.back()) {
                    l.push_back(t[i]);
                }
                else {
                    auto it = lower_bound(l.begin(), l.end(), t[i]);
                    *it = t[i];
                }
            }
            else {
                l.push_back(t[i]);
            }
        }
        
        // 右边最长上升子序列
        for (int i = n - 1;i > m;i--) {
            if (t[i] >= t[m])continue;
            if (r.size()!=0) {
                if (t[i] > r.back()) {
                    r.push_back(t[i]);
                }
                else {
                    auto it = lower_bound(r.begin(), r.end(), t[i]);
                    *it = t[i];
                }
            }
            else {
                r.push_back(t[i]);
            }
        }
        k = max(k, (int)l.size() + (int)r.size() + 1);
    }
    cout << n - k << endl;
}

💭[P1095]守望者的逃离

[NOIP2007 普及组] 守望者的逃离

题目背景

恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。

题目描述

守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。

为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。

守望者的跑步速度为 $17m/s$，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在 $1s$ 内移动 $60m$，不过每次使用闪烁法术都会消耗魔法值 $10$ 点。守望者的魔法值恢复的速度为 $4$ 点每秒，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值 $M$，他所在的初始位置与岛的出口之间的距离 $S$，岛沉没的时间 $T$。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。

注意：守望者跑步、闪烁或休息活动均以秒为单位，且每次活动的持续时间为整数秒。距离的单位为米。

输入格式

输入数据共一行三个非负整数，分别表示 $M$，$S$，$T$。

输出格式

输出数据共两行。

第一行一个字符串 $\texttt{Yes}$ 或 $\texttt{No}$，即守望者是否能逃离荒岛。

第二行包含一个整数。第一行为 $\texttt{Yes}$ 时表示守望者逃离荒岛的最短时间；第一行为 $\texttt{No}$ 时表示守望者能走的最远距离。

样例 #1

样例输入 #1

1

39 200 4

样例输出 #1

1
2

No
197

样例 #2

样例输入 #2

1

36 255 10

样例输出 #2

1
2

Yes
6

提示

对于 $30%$ 的数据，$1 \le T \le 10$，$ 1 \le S \le 100$；

对于 $50%$ 的数据，$1 \le T \le 10^3$，$ 1 \le S \le 10^4$；

对于 $100%$ 的数据，$1 \le T \le 3\times 10^5$，$0 \le M \le 10^3$，$ 1 \le S \le 10^8$。

🎈参考代码

 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

void solve() {
    ll m, s, t;cin >> m >> s >> t;
    vector<ll>f(t + 1);
    f[0] = 0;ll bl = m;
    for (ll i = 1;i <= t;i++) {
        if (bl >= 10) {
            f[i] = f[i - 1] + 60;
            bl -= 10;
        }
        else {
            f[i] = f[i - 1];
            bl += 4;
        }
    }
    for (int i = 1;i <= t;i++) {
        f[i] = max(f[i], f[i - 1] + 17);
    }
    if (f[t] >= s) {
        cout << "Yes\n";
        cout << lower_bound(f.begin(), f.end(), s) - f.begin() << endl;
    }
    else {
        cout << "No\n" << f[t] << endl;
    }
}

💭[P1541]乌龟棋

[NOIP2010 提高组] 乌龟棋

题目背景

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

题目描述

乌龟棋的棋盘是一行 $N$ 个格子，每个格子上一个分数（非负整数）。棋盘第 $1$ 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 $M$ 张爬行卡片，分成 $4$ 种不同的类型（$M$ 张卡片中不一定包含所有 $4$ 种类型的卡片，见样例），每种类型的卡片上分别标有 $1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式

每行中两个数之间用一个空格隔开。

第 $1$ 行 $2$ 个正整数 $N,M$，分别表示棋盘格子数和爬行卡片数。

第 $2$ 行 $N$ 个非负整数，$a_1,a_2,…,a_N$，其中 $a_i$ 表示棋盘第 $i$ 个格子上的分数。

第 $3$ 行 $M$ 个整数，$b_1,b_2,…,b_M$，表示 $M$ 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光$M$张爬行卡片。

输出格式

$1$ 个整数，表示小明最多能得到的分数。

样例 #1

样例输入 #1

1
2
3

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

样例输出 #1

1

73

提示

每个测试点 1s。

小明使用爬行卡片顺序为 $1,1,3,1,2$，得到的分数为 $6+10+14+8+18+17=73$。注意，由于起点是 $1$，所以自动获得第 $1$ 格的分数 $6$。

对于 $30%$ 的数据有 $1≤N≤30,1≤M≤12$。

对于 $50%$ 的数据有 $1≤N≤120,1≤M≤50$，且 $4$ 种爬行卡片，每种卡片的张数不会超过 $20$。

对于 $100%$ 的数据有 $1≤N≤350,1≤M≤120$，且 $4$ 种爬行卡片，每种卡片的张数不会超过 $40$；$0≤a_i≤100,1≤i≤N,1≤b_i≤4,1≤i≤M$。

🎈参考代码

 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

void solve() {
    ll n, m;cin >> n >> m;
    vector<ll>a(n + 1);
    for (ll i = 1;i <= n;i++) {
        cin >> a[i];
    }
    vector<ll>cnt(5);
    for (int i = 0;i < m;i++) {
        ll x;cin >> x;
        cnt[x]++;
    }
    vector<vector<vector<vector<ll>>>>dp(cnt[1] + 1, vector<vector<vector<ll>>>(cnt[2] + 1, vector<vector<ll>>(cnt[3] + 1, vector<ll>(cnt[4] + 1, 0))));

    dp[0][0][0][0] = a[1];
    for (int i = 0;i <= cnt[1];i++) {
        for (int j = 0;j <= cnt[2];j++) {
            for (int k = 0;k <= cnt[3];k++) {
                for (int l = 0;l <= cnt[4];l++) {
                    ll x = i * 1 + j * 2 + k * 3 + l * 4 + 1;   // 走到的格子是x
                    if (i > 0)
                        // 走到x的时候，如果i > 0，那么就可以从i - 1走到i，下面同理
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - 1][j][k][l] + a[x]);
                    if (j > 0)
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - 1][k][l] + a[x]);
                    if (k > 0)
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l] + a[x]);
                    if (l > 0)
                        dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1] + a[x]);
                }
            }
        }
    }
    cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;
}

💭[P1868]饥饿的奶牛

饥饿的奶牛

题目描述

有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。

现用汉语翻译为：

有 $N$ 个区间，每个区间 $x,y$ 表示提供的 $x\sim y$ 共 $y-x+1$ 堆优质牧草。你可以选择任意区间但不能有重复的部分。

对于奶牛来说，自然是吃的越多越好，然而奶牛智商有限，现在请你帮助他。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行两个数 $x,y$，描述一个区间。

输出格式

输出最多能吃到的牧草堆数。

样例 #1

样例输入 #1

1
2
3
4

3
1 3
7 8
3 4

样例输出 #1

1

5

提示

$1 \leq n \leq 1.5 \times 10^5$，$0 \leq x \leq y \leq 3 \times 10^6$。

🎈参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void solve() {
    ll n;cin >> n;
    map<ll, vector<ll>> mp;
    ll my = 0;
    for (ll i = 0;i < n;i++) {
        ll x, y;cin >> x >> y;
        x += 1;y += 1;  // 避免越界
        my = max(my, y);
        mp[y].push_back(x);
    }
    vector<ll>dp(my + 1, 0);
    dp[0] = 0;
    for (ll i = 1;i <= my;i++) {
        dp[i] = dp[i - 1];
        if (mp.count(i)) {
            for (ll j = 0;j < mp[i].size();j++) {
                ll y = mp[i][j];
                dp[i] = max(dp[i], dp[y - 1] + i - y + 1);
            }
        }
    }
    cout << dp[my] << endl;
}

=======待完成部分=======

💭[P2679]子串

[NOIP2015 提高组] 子串

题目描述

有两个仅包含小写英文字母的字符串 $A$ 和 $B$。

现在要从字符串 $A$ 中取出 $k$ 个互不重叠的非空子串，然后把这 $k$ 个子串按照其在字符串 $A$ 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 $B$ 相等？

注意：子串取出的位置不同也认为是不同的方案。

输入格式

第一行是三个正整数 $n,m,k$，分别表示字符串 $A$ 的长度，字符串 $B$ 的长度，以及问题描述中所提到的 $k$，每两个整数之间用一个空格隔开。

第二行包含一个长度为 $n$ 的字符串，表示字符串 $A$。

第三行包含一个长度为 $m$ 的字符串，表示字符串 $B$。

输出格式

一个整数，表示所求方案数。

由于答案可能很大，所以这里要求输出答案对 $1000000007$ 取模的结果。

样例 #1

样例输入 #1

1
2
3

6 3 1 
aabaab 
aab

样例输出 #1

1

2

样例 #2

样例输入 #2

1
2
3

6 3 2 
aabaab 
aab

样例输出 #2

1

7

样例 #3

样例输入 #3

1
2
3

6 3 3 
aabaab 
aab

样例输出 #3

1

7

提示

对于第 1 组数据:$1≤n≤500,1≤m≤50,k=1$;
对于第 2 组至第 3 组数据:$1≤n≤500,1≤m≤50,k=2$;
对于第 4 组至第 5 组数据:$1≤n≤500,1≤m≤50,k=m$;
对于第 1 组至第 7 组数据:$1≤n≤500,1≤m≤50,1≤k≤m$;
对于第 1 组至第 9 组数据:$1≤n≤1000,1≤m≤100,1≤k≤m$;
对于所有 10 组数据:$1≤n≤1000,1≤m≤200,1≤k≤m$。

💭[P2501]数字序列

[HAOI2006] 数字序列

题目描述

现在我们有一个长度为 $n$ 的整数序列 $a$。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。

输入格式

第一行是一个整数，表示序列长度 $n$。
第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 项 $a_i$。

输出格式

第一行输出一个整数，表示最少需要改变多少个数。

第二行输出一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。

样例 #1

样例输入 #1

1
2

4
5 2 3 5

样例输出 #1

1
2

1
4

提示

数据规模与约定

  • 对于 $90%$ 的数据，保证 $n \leq 6 \times 10^3$。
  • 对于 $100%$ 的数据，保证 $1 \leq n \leq 3.5 \times 10^4$，$1 \leq a_i \leq 10^5$。数据保证 $a_i$ 随机生成。

💭[P3336]话旧

[ZJOI2013] 话旧

题目描述

小林跟着银河队选手去了一趟宇宙比赛，耳濡目染，变得学术起来。回来后，他发现世界大变样了。比丘兽究级进化，成了凤凰兽；金先生因为发了一篇 paper，一跃成为教授，也成为了银河队选拔委员会成员。

一日，小林与金教授聊天。金教授回忆起过去的岁月，那些年他学过的电路原理。他曾经对一种三角波很感兴趣，并且进行了一些探究。小林感到很好奇，于是金教授就将课题形式化地说了一遍。

有一定义在 $[0,N]$ 的连续函数 $f(x)$，其中 $N$ 是整数，满足 $f(0)=f(N)=0$，它的所有极值点在整数处取到，且 $f(x)$ 的极小值均是 $0$。对于任意的 $0$ 到 $N-1$ 间的整数 $I$，$f(x)$ 在 $(I, I+1)$ 上是斜率为 $1$ 或 $-1$ 的一次函数。

金先生研究的是，若他知道其中 $K$ 个整点的函数值，那么：

  1. 有多少个函数满足条件？
  2. 满足条件的函数中，$f(x)$ 的最大值，最大能是多少？

小林思考了一下，便想出了很好的算法。那么作为经过多年训练的你呢？

输入格式

第一行包含两个用空格隔开的整数 $N,K$。接下来 $K$ 行，每行两个整数，表示 $x_i$ 和 $f(x_i)$。

输出格式

一行两个整数，分别对应两个问题的答案。考虑到第一问答案可能很大，你只要输出它除以 $19940417$ 的余数。

样例 #1

样例输入 #1

1

2 0

样例输出 #1

1

1 1

样例 #2

样例输入 #2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

6 9
4 2
4 2
2 0
4 2
6 0
5 1
2 0
0 0
0 0

样例输出 #2

1

1 2

提示

  • 对于 $10%$ 的数据，$N \leq 10$。
  • 对于 $20%$ 的数据，$N \leq 50$。
  • 对于 $30%$ 的数据，$N \leq 100$，$K \leq 100$。
  • 对于 $50%$ 的数据，$N \leq 10^3$，$K \leq 10^3$。
  • 对于 $70%$ 的数据，$N \leq 10^5$。
  • 另有 $10%$ 的数据，$K=0$。
  • 对于 $100%$ 的数据，$ 0 \leq N \leq 10^9$，$0 \leq K \leq 10^6$。

💭[P3558]BAJ-Bytecomputer

[POI2013] BAJ-Bytecomputer

题面翻译

给定一个长度为 $n$ 的只包含 $-1,0,1$ 的数列 $a$，每次操作可以使 $a_i\gets a_i+a_{i-1}$，求最少操作次数使得序列单调不降。如果不可能通过该操作使得序列单调不降，请输出 BRAK。

数据范围：$1\le n\le 10^6$。

题目描述

A sequence of integers from the set is given.

The bytecomputer is a device that allows the following operation on the sequence:

incrementing by for any .

There is no limit on the range of integers the bytecomputer can store, i.e., each can (in principle) have arbitrarily small or large value.

Program the bytecomputer so that it transforms the input sequence into a non-decreasing sequence (i.e., such that ) with the minimum number of operations.

输入格式

The first line of the standard input holds a single integer (), the number of elements in the (bytecomputer’s) input sequence.

The second line contains integers () that are the successive elements of the (bytecomputer’s) input sequence, separated by single spaces.

In tests worth 24% of the total points it holds that , and in tests worth 48% of the total points it holds that .

输出格式

The first and only line of the standard output should give one integer, the minimum number of operations the bytecomputer has to perform to make its input sequence non-decreasing, of the single word BRAK (Polish for none) if obtaining such a sequence is impossible.

样例 #1

样例输入 #1

1
2

6
-1 1 0 -1 0 1

样例输出 #1

1

3

💭[P4158]粉刷匠

[SCOI2009] 粉刷匠

题目描述

windy 有 $N$ 条木板需要被粉刷。 每条木板被分为 $M$ 个格子。 每个格子要被刷成红色或蓝色。

windy 每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。

如果 windy 只能粉刷 $T$ 次，他最多能正确粉刷多少格子？

一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

输入格式

第一行包含三个整数，$N,M,T$。

接下来有 $N$ 行，每行一个长度为 $M$ 的字符串，0 表示红色，1 表示蓝色。

输出格式

包含一个整数，最多能正确粉刷的格子数。

样例 #1

样例输入 #1

1
2
3
4

3 6 3
111111
000000
001100

样例输出 #1

1

16

提示

$30%$ 的数据，满足 $1 \le N,M \le 10,0 \le T \le 100$ 。

$100%$ 的数据，满足 $1 \le N,M \le 50,0 \le T \le 2500$

💭[P5301]宝牌一大堆

[GXOI/GZOI2019] 宝牌一大堆

题目描述

麻将是一种传统的博弈游戏，由 $4$ 名玩家参与，轮流摸牌、打牌。在竞技比赛中主要有国标麻将（中国）和立直麻将（日本）两大规则。本题采用一种特别的规则——「宝牌一大堆」规则。

牌型

一副麻将由 $136$ 张牌组成，其中包含 $34$ 种不同的牌，每种各有 $4$ 张。这 $34$ 种牌分别是：
一万到九万、一索到九索、一筒到九筒、东、南、西、北、中、白、发。

doraippai1.png

它们可以组合成不同的牌型：

  • 顺子：$3$ 张数字连续的万，或 $3$ 张数字连续的索，或 $3$ 张数字连续的筒。
  • 刻子：$3$ 张完全一样的牌。
  • 杠子：$4$ 张完全一样的牌。
  • 雀头：$2$ 张完全一样的牌。

其中顺子和刻子统称为面子。

和牌

手牌（一名玩家持有的牌）宣告胜利的状况称为「和牌」。

  • 当玩家持有 $14$ 张牌，并且满足以下三个条件之一时，判定为「和牌」：
    1. 存在一种方案，使得这 $14$ 张牌可以分成 $4$ 组面子、$1$ 组雀头，简记为「$3 \times 4 + 2$」。
    2. 存在一种方案，使得这 $14$ 张牌可以分成 $7$ 组不同的雀头，称为「七对子」。
    3. 这 $14$ 张牌仅由一万、九万、一索、九索、一筒、九筒、东、南、西、北、中、白、发这 $13$ 种牌组成，并且这 $13$ 种牌每种至少有 $1$ 张，称为「国士无双」。
  • 当玩家持有 $15$ 张牌，并且存在一种方案，使得这 $15$ 张牌可以分成 $1$ 组杠子、$3$ 组面子、$1$ 组雀头，判定为和牌。
  • 当玩家持有 $16$ 张牌，并且存在一种方案，使得这 $16$ 张牌可以分成 $2$ 组杠子、$2$ 组面子、$1$ 组雀头，判定为和牌。
  • 当玩家持有 $17$ 张牌，并且存在一种方案，使得这 $17$ 张牌可以分成 $3$ 组杠子、$1$ 组面子、$1$ 组雀头，判定为和牌。
  • 当玩家持有 $18$ 张牌，并且存在一种方案，使得这 $18$ 张牌可以分成 $4$ 组杠子、$1$ 组雀头，判定为和牌。

宝牌

每局游戏还会指定若干张「宝牌」，和牌时，手牌中的每张宝牌会使收益翻一番（会在接下来详细介绍）。

达成分数

由于可以「和牌」的手牌很多，可以给每种判定为「和牌」的手牌定义一个「达成分数」，这个分数等于从所有尚未打出的牌中选出若干张，能够组成该手牌的方法数，再乘上手牌中 $2$ 的「宝牌数」次方。
该分数综合考虑了和牌几率与和牌收益，理论上以分数较高的手牌为目标较好。

例如下图手牌显然是可以「和牌」的，如果目前场上还剩 $3$ 张一万、$4$ 张九万，以及二到八万各 $2$ 张没有打出，宝牌为九万，那么下图手牌的「达成分数」就是 $C_3^3 C_4^3 C_2^2 (C_2^1)^6 2^3 = 2048$，其中 $C$ 表示组合数。

doraippai2.png

特别地，「七对子」和牌的手牌，达成分数额外乘 $7$。「国士无双」和牌的手牌，达成分数额外乘 $13$。

有一天，小 L，小 Y，小 I 和小 W 正在打麻将，路过的雪野和看到了所有已经打出的牌，但不知道任何一名玩家的手牌。也许你已经猜到了下面的剧情— —雪野和想知道在所有尚未打出的牌中，「达成分数」最高的可以「和牌」的手牌有多少分，但是她还要观看麻将比赛，所以这个问题就交给你了。

输入格式

每个测试点包含多组数据，第一行是一个整数 $T$，表示数据组数。注意各组数据之间是互相独立的。

每组数据包含两行，第一行给出场上已经打出的牌，第二行给出该局的所有宝牌。

规定用 $\texttt{1m},\texttt{2m},\dots,\texttt{9m}$ 代表万，$\texttt{1p},\texttt{2p},\dots,\texttt{9p}$ 代表筒，$\texttt{1s},\texttt{2s},\dots,\texttt{9s}$ 代表索，$\texttt E,\texttt S,\texttt W,\texttt N$ 代表东、南、西、北，$\texttt Z,\texttt B,\texttt F$ 代表中、白、发，相邻两张牌之间用一个空格隔开，每行的末尾有一个单独的 $0$ 代表结束。

输出格式

输出文件应包含 $T$ 行，对于每组数据，输出一个整数表示最高分数。

样例 #1

样例输入 #1

1
2
3
4
5

2
0
0
7m 4p 2s 7s 6p 8s 7p 5s 9s 9s 1p 5m 9m 5s 4p 5s E 1p 6s 5p B 4m 6m W 6p 6s E 9s 5p 2s 8s 8p 4m 3s 9m 5p 3s 2s 6s 8s 8p 6p 5m 4s 3m 4s 5s 4s 6m 9s 6p N 5m 7s 4m 2m 2s 6s 3m 7p B B N 1m 3m B 8p F 7p 0
W 4p N 3m 2m B 9m 3p 1p 6p S 4s 5p 8s 4m 5s 2s 3s 0

样例输出 #1

1
2

1308622848
127401984

提示

样例解释

在第一组数据中，没有打出过任何牌，没有宝牌，和「国士无双」分数最高，为 $13 \times 6 \times 4^{12}$。
和「$3 \times 4 + 2$」和「七对子」的分数为 $100663296$ 和 $1959552$。

在第二组数据中，和「$3 \times 4 + 2$」分数最高，为 $127401984$，可以得到该分数的手牌之一为「$\texttt{1m2m3m 7m8m9m 1p2p3p 3p4p5p SS}$」。
和「七对子」的分数为 $125411328$，不存在和「国士无双」的可能。

数据范围

保证已经打出的牌必定是合法的牌，且每种不超过 $4$ 张。宝牌不会重复给出。

测试点编号 $T$ 的规模 已经打出的牌 宝牌数
$1$ $T = 10$ 无特殊限制 $\le 20$ 张
$2$ $T = 100$ 至少包括所有数字为三到七的牌 $\le 20$ 张
$3$ $T = 500$ 每种至少 $2$ 张 $\le 20$ 张
$4$ $T = 500$ 每种至少 $3$ 张 $\le 20$ 张
$5$ $T = 500$ 无特殊限制 $0$ 张
$6$ $T = 1,000$ 无特殊限制 $0$ 张
$7$ $T = 1,000$ 无特殊限制 $\le 20$ 张
$8$ $T = 1,500$ 无特殊限制 $\le 20$ 张
$9$ $T = 2,000$ 无特殊限制 $\le 20$ 张
$10$ $T = 2,500$ 无特殊限制 $\le 20$ 张