题目链接
@[toc]

A - 数字组合

小蒜有 n(1≤n≤20)个正整数,找出其中和为 t(t 也是正整数)的可能的组合方式。如:n=5,5 个数分别为 1,2,3,4,5,t=5;那么可能的组合有 5=1+4和 5=2+3和 5=5三种组合方式。输入格式输入的第一行是两个正整数 n 和 t,用空格隔开,其中 $1 \le n \le 20$, 表示正整数的个数,t 为要求的和 $(1≤t≤1000)$接下来的一行是 n 个正整数,用空格隔开。输出格式和为 t 的不同的组合方式的数目。输出时每行末尾的多余空格,不影响答案正确性
样例输入
5 5
1 2 3 4 5
样例输出
3

定义:
$dp[i][j]$为考虑前$i$个数和为j的组合的个数
初始化:
$dp[i][0]=1$,即不管考虑多少个数,和为0的组合方案数只有一个,就是没有加数。
转移方程:
$dp[i][j] = dp[i - 1][j] + (j - a[i] >= 0 ? dp[i - 1][j - a[i]]:0)$。前$i$个数和为$j$的方案数等于前$i-1$个数和为j的方案数加上前$i-1$个数和为$j-a[i]$的方案数($j-a[i]+a[i]=j$)。

那么所求结果即为考虑前$n$个数和为t的方案数,即为$dp[n][t]$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int a[21];
int dp[21][1001];
int n, t;
int main() {
cin >> n >> t;
for (int i = 1; i <= n; ++i)cin >> a[i];
for (int i = 0; i <= n; ++i)dp[i][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= t; ++j) {
dp[i][j] = dp[i - 1][j] + (j - a[i] >= 0 ? dp[i - 1][j - a[i]]:0);
}
}
cout << dp[n][t];
}

B - 神奇的口袋

有一个神奇的口袋,总的容积是 400,用这个口袋可以变出一些物品,这些物品的总体积必须是 400。小蒜现在有n个想要得到的物品,每个物品的体积分别是$a_1​,a_2\cdots a_n$。小蒜可以从这些物品中选择一些,如果选出的物体的总体积是 400,那么利用这个神奇的口袋,小蒜就可以得到这些物品。现在的问题是,小蒜有多少种不同的选择物品的方式。输入格式输入的第一行是正整数 $n(1≤n≤200)$,表示不同的物品的数目。接下来的 $n$ 行,每行有一个 1 到 400 之间的正整数,分别给出 $a_1​,a_2\cdots a_n$ 的值。输出格式输出不同的选择物品的方式的数目对 10000取模的结果(因为结果可能很大,为了避免高精度计算,只要求对 10000取模的结果)。输出时每行末尾的多余空格,不影响答案正确性
样例输入
3
200
200
200
样例输出
3

定义:
$dp[i][j]$为考虑前$i$个物体体积和为j的组合的个数
初始化:
$dp[i][0]=1$,即不管考虑多少个物品,体积和为0的组合方案数只有一个,就是没有任何物品。
转移方程:
$dp[i][j]=dp[i−1][j]+(j−a[i]>=0?dp[i−1][j−a[i]]:0)$。前i个物品体积和为j的方案数等于前$i-1$个物品体积和为j的方案数加上前$i-1$个物品体积和为$j-a[i]$的方案数($j−a[i]+a[i]=j$)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int a[201];
int dp[201][401];
int n;
constexpr int V = 400, mod = 10000;
int main() {
cin >> n;
for (int i = 1; i <= n; ++i)cin >> a[i];
for (int i = 0; i <= n; ++i) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= V; ++j) {
dp[i][j] = dp[i - 1][j] + (j - a[i] >= 0 ? dp[i - 1][j - a[i]] : 0) % mod;
}
}
cout << dp[n][V] % mod;

}

C - 大盗阿福

阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。这条街上一共有 $N$ 家店铺,每家店中都有一些现金。阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?输入格式输入的第一行是一个整数 $T(T≤50)$,表示一共有 $T$组数据。接下来的每组数据,第一行是一个整数 $N(1≤N≤100,000)$,表示一共有 N 家店铺。第二行是 $N$ 个被空格分开的正整数,表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000。输出格式对于每组数据,输出一行。该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。提示对于第一组样例,阿福选择第 2 家店铺行窃,获得的现金数量为 8。对于第二组样例,阿福选择第 1 和 4 家店铺行窃,获得的现金数量为 10+14=24。输出时每行末尾的多余空格,不影响答案正确性
样例输入
2
3
1 8 2
4
10 7 6 14
样例输出
8
24

定义:
$dp[i]$为考虑前$i$个物品的最大收益
初始化:
$dp[i]$等于只拿第$i$个物品的金额。
转移方程:
$dp[i]=max(dp[i-1],dp[i-2]+a[i])$,即考虑前$i$个物品的最大收益为$max$(拿第$i-1$个物品,拿第$i-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
29
30
31
#include<iostream>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int n, k;
int a[100001];
int dp[100001];
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
}
void init() {
for (int i = 1; i <= n; ++i)dp[i] = a[i];
}
int compute() {
for (int i = 2; i <= n; ++i) {
dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);
}
return dp[n];
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
input();
init();
printf("%d\n", compute());
}
}

D - 开餐馆

蒜头君想开家餐馆. 现在共有 $n$ 个地点可供选择。蒜头君打算从中选择合适的位置开设一些餐馆。这 $n$ 个地点排列在同一条直线上。我们用一个整数序列 $m_1, m_2, \cdots m_n$​ 来表示他们的相对位置。由于地段关系, 开餐馆的利润会有所不同。我们用 $p_i$​ 表示在 $m_i$ 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于$k$。请你帮助蒜头君选择一个总利润最大的方案。
输入格式
标准的输入包含若干组测试数据。输入第一行是整数$T (1 \leq T \leq 1000)$,表明有 $T$ 组测试数据。紧接着有 $T$ 组连续的测试。每组测试数据有 3 行;
第 1 行:地点总数 $n(n \lt 100)$, 距离限制$(0\lt k \lt 1000)$;
第 2 行: n 个地点的位置$m_1,m_2,\cdots m_n(1000000>m_i>0$ 且为整数, 升序排列);
第 3 行: n 个地点的餐馆利润 $p_1,p_2,\cdots p_n(1000>p_i>0$ 且为整数)。
输出格式
对于每组测试数据可能的最大利润。输出时每行末尾的多余空格,不影响答案正确性

定义:
$dp[i]$为考虑前$i$个地点的最大收益
初始化:
$dp[i]=val[i]$,第$i$个地点初始化为只选取当前餐馆。
转移方程:
$dp[i]=max(dp[i],dp[j]+(dis[i]-dis[j]>k?val[j]:0)$

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
#include<iostream>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int n, k;
int val[101];
int dis[101];
int dp[101];
void input() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)scanf("%d", &dis[i]);
for (int i = 1; i <= n; ++i)scanf("%d", &val[i]);
}
void init() {
for (int i = 1; i <= n; ++i)dp[i] = val[i];
}
int compute() {
for (int i = 2; i <= n; ++i) {
//考虑i之前的所有情况
for (int j = 1; j < i; ++j) {
//如果第i个地点和第j个地点距离大于k
if (dis[i] - dis[j] > k) {
//那就可以选取dp[j]的最大情况加上当前地点的收益
dp[i] = max(dp[i], dp[j] + val[i]);
}
else {
dp[i] = max(dp[i], dp[j]);
}
}
}
return dp[n];
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
input();
init();
printf("%d\n", compute());
}
}

E - 最大上升子序列和

一个数的序列 $b_i$​,当 $b_1\lt b_2\lt \cdots \lt b_S$的时候,我们称这个序列是上升的。蒜头君给定了一个序列 $(a_1, a_2, \cdots ,a_N)$,我们可以得到一些上升的子序列 $(a_{i_1}, a_{i_2}, \cdots , a_{i_K})$,这里 $1 \le i_1 < i_2 < … < i_K \le N$。比如,对于序列 $(1, 7, 3, 5, 9, 4, 8)$ ,有它的一些上升子序列,如 $(1, 7), (3, 4, 8)$ 等等。这些子序列中序列和最大为 18,为子序列$(1,3,5,9)$ 的和。你的任务,就是对于给定的序列,求出最大上升子序列和。注意,最长的上升子序列的和不一定是最大的,比如序列 $(100,1,2,3)$ 的最大上升子序列和为 100,而最长上升子序列为 $(1, 2, 3)$ 。
输入格式
输入的第一行是序列的长度 $(1 \le N \le 1000)$。
第二行给出序列中的 N 个整数,这些整数的取值范围都在 0 到 10000(可能重复)。
输出格式
最大上升子序列和。输出时每行末尾的多余空格,不影响答案正确性
样例输入
7
1 7 3 5 9 4 8
样例输出
18

定义:
$dp[i]$为以$s_i$为后缀的最大上升子序列和
初始化:
$dp[i]=0$
转移方程:

1
2
3
if (Data[j]<Data[i] ) {
dp[i] = max(dp[i],dp[j]);
}

从前往后考虑,且$j\lt i$,那么如果$s_j\lt s_i$,那么$dp[j]$所属的子串就有资格作为$dp[i]$的前缀。那么答案为$max(dp[i]),i=1,2,\cdots ,N$,其中,$N$为序列的·长度。

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
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define scanf scanf_s
int Data[1001], dp[1001];
int main(){
int n;
cin >> n;
for (int i = 1; i <= n; ++i)cin >> Data[i];
int Ans = Data[1];
for (int i = 1; i <= n; i++){
//考虑i的所有前缀可能
for (int j = 1; j <= i; j++) {
//如果这个前缀的后缀小于s_i,那这个前缀就有资格作为当前子序列的前缀
if (Data[j]<Data[i] ) {
dp[i] = max(dp[i],dp[j]);
}
}
//加上当前后缀值
dp[i]+= Data[i];
Ans=max(Ans,dp[i]);
}
cout<<Ans;
return 0;
}

F - 魔法少女

前些时间虚渊玄的巨献小圆着实火了一把。 在黑长直(小炎)往上爬楼去对抗魔女之夜时,她遇到了一个问题想请你帮忙。 因为魔女之夜是悬浮在半空的,所以她必须要爬楼,而那座废墟一共有 n 层,而且每层高度不同,这造成小炎爬每层的时间也不同。不过当然,小炎会时间魔法,可以瞬间飞过一层或者两层[即不耗时]。但每次瞬移的时候她都必须要至少往上再爬一层(在这个当儿补充魔力)才能再次使用瞬移。爬每单位高度需要消耗小炎 1 秒时间。 消灭魔女之夜是刻不容缓的,所以小炎想找你帮她找出一种最短时间方案能通往楼顶。
输入格式
第一行一个数字 $N(1 \le N \le 10000)$,代表楼层数量。
接下去 $N$ 行,每行一个数字$(1 \le H \le 100)$,代表本层的高度。
输出格式
输出一行,一个数字 $S$,代表通往楼顶所需的最短时间。输出时每行末尾的多余空格,不影响答案正确性
样例输入
5
3
5
1
8
4
样例输出
1

定义:
$dp[i][0]$为爬到第$i$层且当前不能瞬移的最短时间,$dp[i][1]$为爬到第$i$层且当前可以瞬移的最短时间。
初始化:

1
2
3
4
dp[1][0] = 0;//瞬移到1楼
dp[2][0] = 0;//瞬移到2楼
dp[2][1] = Data[2];//瞬移到1楼再爬到2楼
dp[1][1] = Data[1];//爬到1楼

转移方程:

1
2
3
4
5
6
7
8
9
10
for (int i = 3; i <= n; i++) {
//第i层不能瞬移的最小代价由i-2层瞬移或i-1层瞬移而来
dp[i][0] = min(dp[i - 2][1], dp[i - 1][1]);

dp[i][1] = min(
dp[i - 2][0] + Data[i - 1] + Data[i], min(//从i-2层爬到i-1层再爬到i层
dp[i - 1][0] + Data[i], //从i-1层爬上来
dp[i - 2][1] + Data[i], //从i-2层瞬移到i-1层再爬到i层
));
}

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
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
using namespace std;
int dp[10001][2];
int Data[10001];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &Data[i]);
}
dp[1][0] = 0;
dp[2][0] = 0;
dp[2][1] = Data[2];
dp[1][1] = Data[1];
for (int i = 3; i <= n; i++) {
dp[i][0] = min(dp[i - 2][1], dp[i - 1][1]);
dp[i][1] = min(
dp[i - 2][0] + Data[i - 1] + Data[i], min(
dp[i - 1][0] + Data[i],
dp[i - 2][1] + Data[i]
)
);
}
printf("%d\n", min(dp[n][0], dp[n][1]));
return 0;
}

G - 回文字符串

所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如$”aba”$。当然,我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你,给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成为回文字符串。
输入格式
第一行给出整数 $N(0\lt N \le 100)$。
接下来的 N 行,每行一个字符串,每个字符串长度不超过 1000。
输出格式
每行输出所需添加的最少字符数。输出时每行末尾的多余空格,不影响答案正确性
样例输入
1
Ab3bd
样例输出
2

对于每个无法构成回文的字符,在其相应的位置(即第i个字符的相应位置为倒数第i个字符)添加一个相同字符即可使其构成回文字符,因此,只需要找出字符串中的非回文字符即可(非回文字符指在其相应位置的字符和当前位置字符不同的字符)。比如字符串$abbc$中,第一个字符$a$对应倒数第一个字符$c$,他们不相等,因此$a$和$c$都是非回文字符。
所以我们要在字符串中找到其最长的回文子串,那么这个回文字串对应的非回文字符数将是最少的。
所以为了找到最长回文子串,我们只需要找出原字符串和其反串的最长公共子序列即可。
而求最长公共子序列采用动态规划的方法。
定义:$S$为原串,$T$为反串,$S_i$为$S$的前$i$个字符组成的字串,$T$同理。
定义:
$dp[i][j]$为$S_i$和$T_j$的最长公共子序列。
初始化:
$dp[i][j]=0$
转移方程:

1
2
3
4
5
6
7
8
//如果原串第i个字符和反串第j个字符相同
if (s1[i] == s2[j]){
//那就匹配
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

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
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<memory.h>
using namespace std;
int dp[1001][1001];
#define scanf scanf_s
int main() {
int T;
cin >> T;
while (T--) {
string s1;
cin >> s1;
memset(dp, 0x0, sizeof(dp));
string s2(s1);
reverse(s2.begin(),s2.end());
//为了防止i-1小于0,让i从1开始
//此时dp[i][j]为S_i-1和T_j-1的最长公共子序列
for (int i = 1; i <= s1.size(); i++){
for (int j = 1; j <= s2.size(); j++){
if (s1[i - 1] == s2[j - 1]){
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
printf("%d\n", s1.size() - dp[s1.size()][s1.size()]);
}
return 0;
}

H - 带通配符的字符串匹配

通配符是一类键盘字符,当我们不知道真正字符或者不想键入完整名字时,常常使用通配符代替一个或多个真正字符。通配符有问号 $(?)$ 和星号 $()$ 等,其中,$”?”$ 可以代替一个字符,而 $”“$ 可以代替零个或多个字符。 你的任务是,给出一个带有通配符的字符串和一个不带通配符的字符串,判断他们是否能够匹配。 例如,$1?456$ 可以匹配 $12456、13456、1a456$ ,但是却不能够匹配 $23456、1aa456$ ; $277?8$ 可以匹配 $24457798、237708、27798$。
输入格式
输入有两行,每行为一个不超过 20 个字符的字符串,第一行带通配符,第二行不带通配符。
输出格式
如果两者可以匹配,就输出 $”matched”$ ,否则输出 $”not matched”$ 。输出时每行末尾的多余空格,不影响答案正确性
样例输入
$1
456?$
$11111114567$
样例输出
$matched$
定义:
设带通配符的串为$P$,不带通配符的为$T$。
定义$P_i$为$P$的前i个字符组成的字串,$T$同理。
$dp[i][j]$表示$P_i$和$T_j$是否匹配。
初始化:
空串可以和空串匹配且$”“$也可以和空串匹配,因此由:

1
2
3
4
dp[0][0] = true;
for (int i = 0; s[i] == '*'&&i < s.size(); ++i) {
dp[i + 1][0] = true;
}

因为$dp[0][0]$表示空串,因此$s[0]$对应的为s的第一个字符,即为$S_1$,对应的$dp$位置为$dp[1]$。
转移方程:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for (int i = 0; i < s.size(); ++i) {
for (int j = 0; j < t.size(); ++j) {
switch (s[i]) {
case '?':
//此时表示第i个字符和第j个字符肯定匹配,
//因此S_i和T_j的匹配情况等于S_i-1和T_j-1的匹配情况
dp[i + 1][j + 1] = dp[i][j];
break;
case '*':
dp[i + 1][j + 1] =
dp[i][j + 1] || //*和空串匹配
dp[i][j] || //*和T_j匹配
dp[i + 1][j];//*和T_j-1匹配
break;
default:
//如果当前匹配,那和?效果一样
if (s[i] == t[j]) {
dp[i + 1][j + 1] = dp[i][j];
}
break;
}
}
}

看\
号情况中的dp[i + 1][j],$P_i$和$T_{j-1}$,当$P_i=$时,如果他们匹配了,则表示$P_i$和$T_{j-2},T_{j-3}\cdots T_1$都匹配,因为\可以代替任意字符。
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
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
#define scanf scanf_s
bool dp[22][22];
int main(){
string s, t;
cin >> s >> t;
dp[0][0] = true;
for (int i = 0; s[i] == '*'&&i < s.size(); ++i) {
dp[i + 1][0] = true;
}
for (int i = 0; i < s.size(); ++i) {
for (int j = 0; j < t.size(); ++j) {
switch (s[i]) {
case '?':
dp[i + 1][j + 1] = dp[i][j];
break;
case '*':
dp[i + 1][j + 1] = dp[i][j + 1] || dp[i][j] || dp[i + 1][j];
break;
default:
if (s[i] == t[j]) {
dp[i + 1][j + 1] = dp[i][j];
}
break;
}
}
}
printf(dp[s.size()][t.size()] ? "matched\n" : "not matched\n");
return 0;
}

I - 租用游艇

长江游艇俱乐部在长江上设置了 $n$ 个游艇出租站 $1,2,\cdots,n$。游客可在这些游艇出租站租用游艇,并在 下游 的任何一个游艇出租站归还游艇。游艇出租站 $i$ 到游艇出租站 $j$ 之间的租金为 $r_{i,j}(i\lt j)$。试设计一个算法,计算出从游艇出租站 1 到游艇出租站 $n$ 所需的最少租金。
输入格式
第一行一个整数 $n(1\leq n \leq 200)$,表示游艇出租站的数量。
接下来的 $n−1$ 行是一个半矩阵 $r_{i,j}(1 \leq r_{i,j} \leq 10000)$,表示第 $i$ 个出租站到下游每个出租站的租金。
输出格式
一个整数,表示从游艇出租站 1 到游艇出租站 $n$ 所需的最少租金。输出时每行末尾的多余空格,不影响答案正确性。
样例输入
3
5 15
7
样例输出
12

最短路…

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
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#include<climits>
struct twice {
int point, weight;
twice(int&p, int&w) :point(p), weight(w) { }
};
struct Nodep {
int dis, id;
bool operator<(const Nodep&r)const{
return dis > r.dis;
}
};
vector<twice> Node[201];
inline void input(int n){
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
int dis;
scanf("%d", &dis);
Node[i].emplace_back(j, dis);
}
}
}
inline void work(int n, int s){
register priority_queue<Nodep> Q;
register int now = s;
register int dis[201];
register bool vis[201]{ false };
for (auto&e : dis)
e = INT_MAX;
Q.push({ 0,now }); dis[now] = 0;
while (!Q.empty())
{
now = Q.top().id; Q.pop();
if (vis[now])continue;
vis[now] = true;
for (auto e : Node[now])
{
if (!vis[e.point])
{
if (dis[e.point] > e.weight + dis[now])
{
dis[e.point] = e.weight + dis[now];
Q.push({ dis[e.point],e.point });
}
}
}
}
printf("%d\n", dis[n]);
}
int main(){
int n;
scanf("%d", &n);
input(n);
work(n, 1);
return 0;
}