本题的DP划分方式比较常用，建议记忆。根据序列最小值是否为0进行划分集合，而非01背包问题。
正文
在火影忍者的世界里，令敌人捉摸不透是非常关键的。
我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。
针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
那么问题来了，假设鸣人的查克拉能量为 M，他影分身的个数最多为 N，那么制造影分身时有多少种不同的分配方法？
注意：
- 影分身可以分配0点能量。
- 分配方案不考虑顺序，例如：M=7,N=3，那么 (2,2,3) 和 (2,3,2) 被视为同一种方案。
输入格式
第一行是测试数据的数目 t。
以下每行均包含二个整数 M 和 N，以空格分开。
输出格式
对输入的每组数据 M 和 N，用一行输出分配的方法数。
数据范围
0 ≤ t ≤ 20,
1 ≤ M,N ≤ 10
数据保证一定有解。
输入样例：
输出样例：
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
| #include<bits/stdc++.h>
using namespace std;
const int N = 20;
int T;
int m,n;
int f[N][N];
int main()
{
cin >> T;
while(T--)
{
memset(f,0,sizeof f);
cin >> m >> n;
f[0][0] = 1;
for(int i = 0;i <= m;i++)
{
for(int j = 1;j <= n;j++)
{
f[i][j] = f[i][j - 1];
if(i >= j) f[i][j] += f[i - j][j];
}
}
cout << f[m][n] << endl;
}
return 0;
}
|
本题的是01背包的变种，总和换成了余数的形式，本质上分析方式还是相同的，需要注意负数取余问题。
正文
由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。
在这一天，Dzx可以从糖果公司的 N 件产品中任意选择若干件带回家享用。
糖果公司的 N 件产品每件都包含数量不同的糖果。
Dzx希望他选择的产品包含的糖果总数是 K 的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。
当然，在满足这一条件的基础上，糖果总数越多越好。
Dzx最多能带走多少糖果呢？
注意：Dzx只能将糖果公司的产品整件带走。
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行 1 个整数，表示糖果公司该件产品中包含的糖果数目，不超过 1000000。
输出格式
符合要求的最多能达到的糖果总数，如果不能达到 K 的倍数这一要求，输出 0。
数据范围
1 ≤ N ≤ 100,
1 ≤ K ≤ 100,
输入样例：
输出样例：
样例解释
Dzx的选择是2+3+4+5=14，这样糖果总数是7的倍数，并且是总数最多的选择。
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<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,k;
int w[N];
int f[N][N];
int main()
{
cin >> n >> k;
memset(f,-0x3f,sizeof f);
f[0][0] = 0;
for(int i = 1;i <= n;i++)
{
cin >> w[i];
}
for(int i = 1;i <= n;i++)
{
for(int j = 0;j <= k;j++)
{
f[i][j] = max(f[i - 1][j],f[i - 1][((j - w[i]) % k + k) % k] + w[i]);
}
}
cout << f[n][0] << endl;
return 0;
}
|
本题是一道区间DP，难点是转化成求最长回文子序列问题，区间DP一般根据左右端点划分成4种情况，这里也差不多。其中需要注意：找不到所划分部分的转移方程，应该考虑它的父集。
正文
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入格式
共一行，包含一个由大写字母ABCD构成的字符串，表示现在看到的密码串。
输出格式
输出一个整数，表示至少脱落了多少个种子。
数据范围
输入字符串长度不超过1000
输入样例1：
输出样例1：
输入样例2：
输出样例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
| #include<bits/stdc++.h>
using namespace std;
const int N = 1010;
string str;
int f[N][N];
int main()
{
cin >> str;
int n = str.size();
for(int len = 1;len <= n;len++)
{
for(int l = 0;l + len - 1 < n;l++)
{
int r = l + len - 1;
if(len == 1) f[l][r] = 1;
else
{
if(str[l] == str[r]) f[l][r] = f[l + 1][r - 1] + 2;
f[l][r] = max(f[l][r],f[l + 1][r]);
f[l][r] = max(f[l][r],f[l][r - 1]);
f[l][r] = max(f[l][r],f[l + 1][r - 1]);
}
}
}
cout << n - f[0][n - 1] << endl;
return 0;
}
|
本题是一道树形DP，搞清楚写法就不难，把树形DP看成深搜来写，其中dp数组用来存数据。
正文
在X森林里，上帝创建了生命之树。
他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。
上帝要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a,b，都存在一个点列 {a,v1,v2,…,vk,b} 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。
在这个前提下，上帝要使得 S 中的点所对应的整数的和尽量大。
这个最大的和就是上帝给生命之树的评分。
经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。
但是由于 atm 不擅长计算，他不知道怎样有效的求评分。
他需要你为他写一个程序来计算一棵树的分数。
输入格式
第一行一个整数 n 表示这棵树有 n 个节点。
第二行 n 个整数，依次表示每个节点的评分。
接下来 n−1 行，每行 2 个整数 u,v，表示存在一条 u 到 v 的边。
由于这是一棵树，所以是不存在环的。
树的节点编号从 1 到 n。
输出格式
输出一行一个数，表示上帝给这棵树的分数。
数据范围
1 ≤ n ≤ 10^5,
每个节点的评分的绝对值均不超过 10^6。
输入样例：
1
2
3
4
5
6
| 5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
|
输出样例：
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<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10,M = 2 * N;
int n;
int w[N];
int h[N],ne[M],e[M],idx;
LL f[N];
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void dfs(int u,int p)
{
f[u] = w[u];
for(int i = h[u];~i;i = ne[i])
{
int j = e[i];
if(j != p)
{
dfs(j,u);
f[u] += max(0ll,f[j]);
}
}
}
int main()
{
cin >> n;
memset(h,-1,sizeof h);
for(int i = 1;i <= n;i++) cin >> w[i];
for(int i = 0;i < n - 1;i++)
{
int a,b;
cin >> a >> b;
add(a,b),add(b,a);
}
dfs(1,-1);
LL res = INT_MIN;
for(int i = 1;i <= n;i++) res = max(res,f[i]);
cout << res << endl;
return 0;
}
|
本题难点其实不在于DP，而是需要根据裴蜀定理得出：只有所有包子数公因数为1时才有解，故其他情况为INF。本身是一道完全背包问题，代码中用到了斜率优化(代换)和降维(对代码作等价变形)。
正文
小明几乎每天早晨都会在一家包子铺吃早餐。
他发现这家包子铺有 N 种蒸笼，其中第 i 种蒸笼恰好能放 Ai 个包子。
每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买 X 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X 个包子。
比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。
当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。
比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。
而顾客想买 7 个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入格式
第一行包含一个整数 N。
接下来 N 行，每行包含一个整数 Ai。
输出格式
输出一个整数代表答案。
如果凑不出的数目有无限多个，输出INF。
数据范围
1 ≤ N ≤ 100,
1 ≤ Ai ≤ 100
输入样例1：
输出样例1：
输入样例2：
输出样例2：
样例解释
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
对于样例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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<bits/stdc++.h>
using namespace std;
const int N = 110,M = 10010;
int n;
int a[N];
bool f[M];
int gcd(int a,int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
cin >> n;
int d = 0;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
d = gcd(d,a[i]);
}
if(d != 1)
{
cout << "INF" << endl;
}else
{
f[0] = true;
for(int i = 1;i <= n;i++)
{
for(int j = a[i];j < M;j++)
{
f[j] |= f[j - a[i]];
}
}
int res = 0;
for(int i = 0;i < M;i++)
{
if(!f[i]) res++;
}
cout << res << endl;
}
return 0;
}
|
本题也是一道区间DP，是密码脱落的扩展，除了基于单串的左右端点划分，还需要根据分界点划分连串情况(可以记忆)。
正文
Hecy 又接了个新任务：BE 处理。
BE 中有一类被称为 GBE。
以下是 GBE 的定义：
空表达式是 GBE
如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE
如果 A 与 B 都是 GBE，那么 AB 是 GBE
下面给出一个 BE，求至少添加多少字符能使这个 BE 成为 GBE。
注意：BE 是一个仅由(、)、[、]四种字符中的若干种构成的字符串。
输入格式
输入仅一行，为字符串 BE。
输出格式
输出仅一个整数，表示增加的最少字符数。
数据范围
对于所有输入字符串，其长度小于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
| #include<bits/stdc++.h>
using namespace std;
const int N = 110,INF = INT_MAX;
string str;
int f[N][N];
bool check(char a,char b)
{
if(a == '(' && b == ')') return true;
if(a == '[' && b == ']') return true;
return false;
}
int main()
{
cin >> str;
int n = str.size();
for(int len = 1;len <= n;len++)
{
for(int i = 0;i + len - 1 < n;i++)
{
int j = i + len - 1;
f[i][j] = INF;
if(check(str[i],str[j])) f[i][j] = min(f[i][j],f[i + 1][j - 1]);
else
{
f[i][j] = min(f[i][j],f[i + 1][j] + 1);
f[i][j] = min(f[i][j],f[i][j - 1] + 1);
f[i][j] = min(f[i][j],f[i + 1][j - 1] + 2);
}
for(int k = i;k < j;k++)
{
f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j]);
}
}
}
cout << f[0][n - 1] << endl;
return 0;
}
|
本题是一道树形DP，在大臣的旅费中我们使用两次dfs的方式求得树的直径，而这题中我们用更为泛用的一种方式求树的直径，别称换根法，实际上就是先求一条最长距离，再求一条次长距离，取其之和。虽然不是裸题，但可以当作一种模型记忆。
正文
W 市的交通规划出现了重大问题，市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。
但由于人员不足，W 市市长决定只在最需要安排人员的路口安排人员。
具体来说，W 市的交通网络十分简单，由 n 个交叉路口和 n−1 条街道构成，交叉路口路口编号依次为 0,1,…,n−1 。
任意一条街道连接两个交叉路口，且任意两个交叉路口间都存在一条路径互相连接。
经过长期调查，结果显示，如果一个交叉路口位于 W 市交通网最长路径上，那么这个路口必定拥挤不堪。
所谓最长路径，定义为某条路径 p=(v1,v2,…,vk)，路径经过的路口各不相同，且城市中不存在长度大于 k 的路径（因此最长路径可能不唯一）。
因此 W 市市长想知道哪些路口位于城市交通网的最长路径上。
输入格式
第一行包含一个整数 n。
之后 n−1 行每行两个整数 u,v，表示编号为 u 和 v 的路口间存在着一条街道。
输出格式
输出包括若干行，每行包括一个整数——某个位于最长路径上的路口编号。
为了确保解唯一，请将所有最长路径上的路口编号按编号顺序由小到大依次输出。
数据范围
1 ≤ n ≤ 2×10^5
输入样例：
1
2
3
4
5
6
7
8
9
10
| 10
0 1
0 2
0 4
0 6
0 7
1 3
2 5
4 8
6 9
|
输出样例：
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
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10,M = 2 * N;
int n;
int h[N],ne[M],e[M],idx;
int d1[N],d2[N],p1[N],up[N];
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
LL maxd;
void dfs_d1(int u,int father)
{
for(int i = h[u];~i;i = ne[i])
{
int j = e[i];
if(j != father)
{
dfs_d1(j,u);
int dist = d1[j] + 1;
if(dist > d1[u])
{
d2[u] = d1[u],d1[u] = dist;
p1[u] = j;
}else if(dist > d2[u]) d2[u] = dist;
}
}
maxd = max(maxd,d1[u] * 1ll + d2[u]);
}
void dfs_up(int u,int father)
{
for(int i = h[u];~i;i = ne[i])
{
int j = e[i];
if(j != father)
{
up[j] = up[u] + 1;
if(p1[u] == j) up[j] = max(up[j],d2[u] + 1);
else up[j] = max(up[j],d1[u] + 1);
dfs_up(j,u);
}
}
}
int main()
{
cin >> n;
memset(h,-1,sizeof h);
for(int i = 0;i < n - 1;i++)
{
int a,b;
cin >> a >> b;
add(a,b),add(b,a);
}
dfs_d1(0,-1);
dfs_up(0,-1);
for(int i = 0;i < n;i++)
{
int d[3] = {d1[i],d2[i],up[i]};
sort(d,d + 3);
if(maxd == d[1] + d[2]) cout << i << endl;
}
return 0;
}
|
本题说是DP问题，其实更接近思维题。因为推导出的转移方程，是一个变系数线性方程，其中比较跳跃的思维是：将状态转移表示成矩阵变换，再使用快速幂加速矩阵乘法。应该当作题源记忆，实际遇到很难想出来。
正文
赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！
我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。
假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。
atm想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多，请输出模 109+7 的结果。
输入格式
第一行包含两个整数 n,m，分别表示骰子的数目和排斥的组数。
接下来 m 行，每行两个整数 a,b，表示 a 和 b 数字不能紧贴在一起。
输出格式
共一个数，表示答案模 109+7 的结果。
数据范围
1 ≤ n ≤ 10^9,
1 ≤ m ≤ 36,
1 ≤ a,b ≤ 6
输入样例：
输出样例：
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 6,mod = 1e9 + 7;
int n,m;
int f[N][N] = {4,4,4,4,4,4};
int A[N][N];
int get_op(int x)
{
if(x >= 3) return x - 3;
return x + 3;
}
void mult(int c[][N],int a[][N],int b[][N])
{
int t[N][N] = {0};
for(int i = 0;i < N;i++)
{
for(int j = 0;j < N;j++)
{
for(int k = 0;k < N;k++)
{
t[i][j] = (t[i][j] + (LL)a[i][k] * b[k][j]) % mod;
}
}
}
memcpy(c,t,sizeof t);
}
int main()
{
cin >> n >> m;
for(int i = 0;i < 6;i++)
{
for(int j = 0;j < 6;j++) A[i][j] = 4;
}
while(m--)
{
int a,b;
cin >> a >> b;
a--,b--;
A[a][get_op(b)] = 0;
A[b][get_op(a)] = 0;
}
for(int k = n - 1;k;k >>= 1)
{
if(k & 1) mult(f,f,A);
mult(A,A,A);
}
int res = 0;
for(int i = 0;i < N;i++) res = (res + f[0][i]) % mod;
cout << res << endl;
return 0;
}
|
wechat
