有严格位置依赖的二维动态规划的一维空间优化
我们以最长公共子序列的空间优化为例：
其位置依赖关系为：左上dp[i-1][j-1] , 上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
|
//滚动数组一维空间优化
void solvepromoted()
{
string s1,s2;
cin >> s1 >> s2;
int n = s1.size();
int m = s2.size();
s1 = "#" + s1;
s2 = "@" + s2;
int dp[m+1];
int backup,leftup;
//初始化dp[0][j]
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)
{
//左上初始化:每一行刚开始的dp[i][0]
leftup = 0;
for(int j=1;j<=m;j++)
{
backup = dp[j];//正序遍历，此时的backup是下一列的左上
if(s1[i]==s2[j])
{
dp[j] = leftup + 1;//左上
}
else
{
dp[j] = max(dp[j-1],dp[j]);//上 和 左
}
leftup = backup;//滚动更新
}
}
cout << dp[m];
}
|
背包DP
普通0/1背包
小 K 有 N 项工作等待完成，第 i 项工作需要花 t_i 单位时间，必须在 d_i 时刻或之前完成，报酬为 p_i。假设小 K 工作时刻从 0 开始，且同一时刻只能做一项工作、工作一旦开始则不可中断或切换至其他工作，请你帮小 K 规划一下如何选择合适的工作，使小 K 可以获得最多的报酬。
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
|
struct node
{
// 需要时间 截止时间 完成贡献
int t,d,p;
};
void solve()
{
int n;
cin >> n;
vector<node> a;
for(int i=0;i<n;i++)
{
int t,d,p;
cin >> t >> d >> p;
if (t>d) continue; // 如果需要时间在截止时间之后则无效
a.push_back({t,d,p});
}
n = a.size();
sort(a.begin(),a.end(),[&](node x, node y)
{
// 贪心
if (x.d != y.d) return x.d < y.d; // 优先安排截止时间紧迫的任务
if (x.t != y.t) return x.t < y.t; // 再优先安排花费时间少的任务
return x.p > y.p; // 最后优先安排贡献多的任务
});
vector<int> dp(5010); // dp[i]表示截止至i时间前最多能获得多少报酬
for (int i=0;i<n;i++)
{
auto [t,d,p] = a[i];
for(int j=d;j>=t;j--) // 0/1背包，当前任务做还是不做
{
dp[j] = max(dp[j], dp[j-t] + p);
}
}
int hi = 0;
for (int i=0;i<=5000;i++) hi = max(hi,dp[i]);
cout << hi << endl;
}
|
0/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
|
const int N = 55;
const int M = 510;
int cost1[N],cost2[N],val[N];
void solve()
{
int v,m;
cin >> v >> m;
int n;
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> cost1[i] >> cost2[i] >> val[i];
}
int dp[v+1][m+1];
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)
{
for(int j=v;j>=cost1[i];j--)
{
for(int k=m;k>=cost2[i];k--)
{
dp[j][k] = max(dp[j][k],dp[j-cost1[i]][k-cost2[i]]+val[i]);
}
}
}
cout << dp[v][m];
}
|
完全背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
long long val[N];
long long time_[N];
long long dp[N];//dp[i][j]表示在i个数j空间下能采到草药的最大价值
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> t >> m;
for(int i=1;i<=m;i++)
{
cin >> time_[i] >> val[i];
}
dp[0]=0;
for(int i=1;i<=m;i++)
for(int j=time_[i];j<=t;j++)
{
dp[j] = max(dp[j-time_[i]]+val[i],dp[j]);
}
cout << dp[t];
return 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
|
const int N = 110;
vector<pair<int,int>> arr[N];
int main()
{
int n,m;
cin >> m >> n;
int w,v,g;
set<int> group;
for(int i=1;i<=n;i++){
cin >> w >> v >> g;
group.insert(g);
arr[g].push_back({w,v});
}
int dp[m+1] = {0};
for(auto x:group){
for(int j=m;j>=0;j--){
for(int k=0;k<arr[x].size();k++){
if(j>=arr[x][k].first){
dp[j] = max(dp[j],dp[j-arr[x][k].first]+arr[x][k].second);
}
}
}
}
cout << dp[m];
return 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
44
45
46
|
const int N = 1000005;//此时的数值大小要尽量大，因为二进制拆分后，需要的数组大小可能会大于原数据范围。
int dp[N];
int val[N],cost[N];
int n;
void solve()
{
int curhr,curmin;
int lhr,lmin;
char dot;
cin >> curhr >> dot >> curmin;
cin >> lhr >> dot >> lmin;
int time = (lhr - curhr)*60 + (lmin - curmin);
cin >> n;
int temp = 0;
for(int i=1;i<=n;i++)
{
int ti,beauti,cnt;
cin >> ti >> beauti >> cnt;
if(cnt==0)//将完全背包转化为分组背包
{
cnt = time/ti;
}
// 二进制拆分优化O(log cnt)
for(int k=1;k<=cnt;k<<=1)
{
temp++;
val[temp] = k * beauti;
cost[temp] = k * ti;
cnt -= k;
}
if(cnt>0)
{
temp++;
val[temp] = cnt * beauti;
cost[temp] = cnt * ti;
}
}
for(int i=1;i<=temp;i++)
{
for(int j=time;j>=cost[i];j--)
{
dp[j] = max(dp[j],dp[j-cost[i]]+val[i]);
}
}
cout << dp[time];
}
|
区间DP
基于两侧端点讨论的可能性展开：
建立dp[L][R]分解子问题至最小子区间，建立缓存表。
将整个序列的问题转化为每个子区间的问题
常见思路：
1.初始化dp[l][r]的两种情况（一般情况下）：边界相同l==r与区间长度为2即l+1=r的情况
2.前期初始化操作后，定义区间起始长度为len=3，再枚举左端点l，计算右端点。
3.建立dp缓存表，搞清楚位置依赖关系，写出状态转移方程，不断扩张边界。
通过插入字符使得字符串变为回文串的最小操作次数
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
|
int dp[N][N];//dp[l][r]代表将原字符串s[l-r]范围的字串转换成回文串所需要的最小操作次数
void solve()
{
string s;
cin >> s;
int n = s.size();
s = "#" + s;
for(int l=1;l<=n-1;l++)
{
dp[l][l+1] = s[l] == s[l+1] ? 0 : 1;
}
for(int len=3;len<=n;len++)
{
for(int l=1;l<=n-len+1;l++)
{
int r = l + len - 1;
if(s[l]==s[r])
{
dp[l][r] = dp[l+1][r-1];
}
else
{
dp[l][r] = min(dp[l+1][r],dp[l][r-1]) + 1;
}
}
}
cout << dp[1][n];
}
|
预测赢家
有两个玩家，给定一个数字序列，每次取序列的左/右端点的值作为收入，现在玩家一是先手，可以确定的是每个玩家都会以最优方式取数，玩家一是否有必胜的条件，如果有输出true否则输出false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
int dp[N][N];//dp[l][r]代表在arr[l~r]区间进行游戏，玩家一所能获得的最大分数
int sum;
int n;
vector<int> arr(N);
void solve()
{
cin >> n;
for(int i=1;i<=n;i++) cin >> arr[i];
for(int l=1;l<=n;l++) dp[l][l] = arr[l];
for(int l=1;l<=n-1;l++) dp[l][l+1] = max(arr[l],arr[l+1]);
for(int len=3;len<=n;len++)//区间长度
{
for(int l=1;l<=n-len+1;l++)
{
int r = l + len - 1;
int chooseleft = arr[l]+min(dp[l+1][r-1],dp[l+2][r]);
int chooseright = arr[r]+min(dp[l+1][r-1],dp[l][r-2]);
dp[l][r] = max(chooseleft,chooseright);
}
}
sum = accumulate(arr.begin(),arr.end(),0);
int player2 = sum - dp[1][n];
cout << (player2 > dp[1][n] ? "false" : "true");
}
|
转移方程的解释：玩家一有两种选择：取左端或右端，取走一端后，会进入下一种情况(以取走左端为例):此时玩家二做选择，其一定会选择对他来说收益最大的值，所以此时玩家一会选走更小的一个数字即min(dp[l+1][r-1],dp[l+2][r])
基于范围上划分点的可能性展开
在这种区间 DP 的思路中，我们同样定义了 dp[l][r] 来表示区间 [l, r] 上的某种最优解。与基于两侧端点讨论的可能性展开不同，这里状态更新是通过枚举区间内的划分点 m（l <= m < r）来实现的。我们将原区间 [l, r] 划分为两个子区间 [l, m] 和 [m + 1, r]，然后根据这两个子区间的结果来更新 dp[l][r]。
常见思路如下：
- 初始化
dp[l][r] 的两种情况（一般情况下）：边界相同 l == r 与区间长度为 2 即 l + 1 == r 的情况。
- 前期初始化操作后，定义区间起始长度为
len = 3，再枚举左端点 l，计算右端点 r = l + len - 1。
- 对于每个区间
[l, r]，枚举划分点 m（l <= m < r），根据子区间 [l, m] 和 [m + 1, r] 的结果更新 dp[l][r]。
要注意划分点的性质：
情况一：划分点 m 满足 l + 1 <= m < r，讨论 dp[l][m] 和 dp[m][r]
当问题可以通过将区间 [l, r] 划分为两个相邻且无重叠的子区间 [l, m] 和 [m, r]，并且在合并这两个子区间的解时，需要考虑两个子区间之间的相互作用，同时不希望子区间出现长度为 0 的情况时，使用这种划分方式。
情况二：划分点 m 满足 l <= m < r，讨论 dp[l][m] 和 dp[m + 1][r]
当问题可以通过将区间 [l, r] 划分为两个相邻且无重叠的子区间 [l, m] 和 [m + 1, r]，并且允许其中一个子区间的长度为 1（即 m 可以等于 l）时，使用这种划分方式。这种情况通常在一些括号匹配、字符串处理等问题中出现，因为在这些问题中，一个单独的元素也可能是一个有效的子问题。
其中情况二更为常见。
多边形三角剖分的最低得分
你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 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
|
const int N = 1e4;
const int M = 0;
//区间DP
//基于范围上的划分点的可能性展开
int dp[N][N];
vector<int> values(N);
int n;
void solve()
{
cin >> n;
for(int i=1;i<=n;i++) cin >> values[i];
for(int len = 3;len <= n;len++)
{
for(int l=1;l<=n-len+1;l++)
{
int r = l + len - 1;
dp[l][r] = INF;//枚举区间内划分点前初始化为INF，使得dp[l][r]在区间内不断作最优更新
for(int m=l+1;m<=r-1;m++)
{
dp[l][r] = min(dp[l][r],dp[l][m]+dp[m][r]+values[l]*values[m]*values[r]);
}
}
}
cout << dp[1][n];
}
|
石子合并
在一个圆形操场的四周摆放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
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
|
//区间DP
//基于范围上的划分点的可能性展开
//NOI 1995 石子合并
//N = MAXN * 2 需要化环为链
int dpmax[N][N];// dp[l][r]表示将区间[L,R]的石子合并所能获得的最大分数
int dpmin[N][N];// dp[l][r]表示将区间[L,R]的石子合并所能获得的最小分数
int n;
int prefix[N];
int stone[N];
void solve()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> stone[i];
stone[n+i] = stone[i];//化环为链
}
for(int i=1;i<=2*n;i++)//dp[l][m] 和 dp[m][r]两堆石子合并的贡献为prefix[r] - prefix[l-1]!
{
prefix[i] = prefix[i-1] + stone[i];
}
//分别初始化 len = 1 和 len = 2 的状态
for(int l=1;l<=2*n;l++)
{
dpmax[l][l] = dpmin[l][l] = 0;
}
for(int l=1;l<=2*n-1;l++)
{
dpmax[l][l+1] = dpmin[l][l+1] = stone[l] + stone[l+1];
}
//len还是3~n不变，但是左右区间的枚举是在2*n区域内进行
for(int len = 3;len <= n;len++)
{
for(int l=1;l<=2*n-len+1;l++)
{
int r = l + len - 1;
dpmax[l][r] = NINF;
dpmin[l][r] = INF;
for(int m=l;m<=r-1;m++)
{
dpmax[l][r] = max(dpmax[l][r],dpmax[l][m]+dpmax[m+1][r]+prefix[r]-prefix[l-1]);
dpmin[l][r] = min(dpmin[l][r],dpmin[l][m]+dpmin[m+1][r]+prefix[r]-prefix[l-1]);
}
}
}
int ansmin = INF;
int ansmax = NINF;
// 枚举所有长度为 n 的区间，找出最小和最大得分
for (int i = 1; i <= n; i++)
{
// -1 是因为i ~ i + n - 1恰好包含了n个数
ansmin = min(ansmin,dpmin[i][i+n-1]);
ansmax = max(ansmax,dpmax[i][i+n-1]);
}
cout << ansmin << endl << ansmax << endl;
}
|
括号区间匹配
给定一个由 ‘[’ ，’]’，’(’，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。例如当前串是 “([[])"，那么插入一个’]‘即可满足。数据范围：字符串长度满足 1≤n≤100 1≤n≤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
|
const int N = 110;
const int M = 0;
int dp[N][N];//dp[l][r]表示区间[l,r]的最小插入括号数
string s;
void solve()
{
cin >> s;
int n = s.size();
s = "#" + s;
for(int l=1;l<=n;l++) dp[l][l] = 1;
for(int len=2;len<=n;len++)
{
for(int l=1;l<=n-len+1;l++)
{
int r = l + len - 1;
dp[l][r] = INF;
if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))
{
dp[l][r] = min(dp[l][r],dp[l+1][r-1]);//p1
}
for(int m=l;m<=r-1;m++)
{
dp[l][r] = min(dp[l][r],dp[l][m]+dp[m+1][r]);//p2
}
//dp[l][r] = min(p1,p2)
}
}
cout << dp[1][n];
}
|
树形DP
树形dp的主要实现形式dfs，在dfs中dp，主要的实现形式是dp[i][j][0/1]，i是以i为根的子树，j是表示在以i为根的子树中选择j个子节点，0表示这个节点不选，1表示选择这个节点，有的时候j或0/1这一维可以压掉
基本有以下两类树形DP（仅作为示例，揭示一种思想，题目中的树形DP的写法千变万化）
选择节点类（没有上司的舞会）
$$
\begin{cases}
dp[i][0] = dp[j][1] \\
dp[i][1] = max/min(dp[i][0],dp[j][1])
\end{cases}
$$树形背包类（选课）
$$
\begin{cases}
dp[v][k] = dp[u][k] + val \\
dp[u][k] = max/min(dp[v][k-1],dp[u][k])
\end{cases}
$$选课
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 N 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 M 门课程学习，问他能获得的最大学分是多少？
第一行有两个整数 N , M用空格隔开。( 1 <= N <= 300 , 1 <= M <= 300 )
接下来的 N 行,第 i+1 行包含两个整数 k_i 和 s_i, k_i 表示第I门课的直接先修课，s_i 表示第I门课的学分。若 k_i=0表示没有直接先修课（1 <= k_i <= N , 1 <= s_i <= 20）
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
|
const int N = 500;
const int M = 0;
struct node
{
int to,next;
}edge[N<<1];
int cnt = 0;
vector<int> head(N);
void add(int u,int v)
{
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u]= cnt;
}
/*
设dp[i][j]表示选择以i为根的子树中j个课程,所能获得的最大学分。
u代表当前根节点，cur代表其选择的节点的总额。
*/
vector<int> val(N);//存储点权
vector<vector<int>> dp(N,vector<int>(N,0));
int n,m;
void dfs(int u,int cur)//选到以u为根的子树，此时已经选择了cur个课程
{
if(cur<=0) return;
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
//先更新点权，在进行状态转移(dfs)
for(int k=0;k<cur;k++)
{
//可以选择0~cnt-1的课程，-1是因为根节点u是必选的
dp[v][k] = dp[u][k] + val[v];
}
dfs(v,cur-1);
for(int k=1;k<=cnt;k++)
{
//这里是把子树的值赋给了根节点，因为u选择k个点所以v只能选择k-1个点。
dp[u][k] = max(dp[u][k],dp[v][k-1]);
}
}
}
void solve()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
{
int u;
cin >> u >> val[i];
add(u,i);
}
dfs(0,m);
cout << dp[0][m];
}
|
二叉苹果树
有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）
这棵树共有 N 个结点（叶子点或者树枝分叉点），编号为 1∼N，树根编号一定是 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
36
37
38
39
40
41
42
43
44
|
int n,q;
// dp[i][j]表示以节点i为根节点的子树中，保留j个树枝所能保留的最大苹果数量
vector<vector<int>> dp(N,vector<int>(N,0));
void dfs(int u,int fa)
{
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to; // 此边连接到的节点
int w = edge[i].w; // 此边上的苹果数量
if(v!=fa)
{
// 以v为根节点，保留1个树枝（即当前连接u和v的边）时，能保留的苹果数就是边权w，也就是下放了边权到v节点上
dp[v][1] = w;
dfs(v,u);
// 树上分组背包
// 对于以u为根的子树，枚举要保留的树枝数量j，从q递减到1
for(int j = q;j >= 1; j--)
{
// 对于以v为根的子树，枚举要保留的树枝数量k，从0到j
for(int k = 0;k <= j;k++)
{
// 更新dp[u][j]的值，取当前值和从以v为根的子树保留k个树枝，
// 以u为根的子树除了v子树部分保留j - k个树枝的苹果数之和的最大值
if((j!=k&&j!=1)||u==1)
dp[u][j] = max(dp[u][j],dp[v][k]+dp[u][j-k]);
}
}
}
}
}
void solve()
{
// 保留Q个树枝
cin >> n >> q;
for(int i=1;i<=n-1;i++)
{
int u,v,w;
cin >> u >> v >> w;
add(u,v,w);
add(v,u,w);
}
dfs(1,-1);
cout << dp[1][q];
}
|
状压DP
设计一个整型可变参数status，利用status的位信息，来表示：
某个样本是否还能继续使用，然后利用这个信息进行尝试，递归求解（记忆化搜索）
如果有K个样本，那么表示这些样本的状态数量就是2^{K}
所以可变参数status的范围是：[0 ,2^{K} - 1]
样本每增加一个，状态的数量都是指数级增长，故状压DP能解决的问题往往样本数据量不大，基本都在20个以内(10^{6})
可以根据题目数据情况选择是否使用第0位比特位(最好统一都从0开始)，如果样本数n接近20，应选择使用0位比特位，即所有数据转为下标从0开始，避免超时
GEPPETTO
Geppetto 用 N(1 <= N <= 20) 种原材料做比萨，每种原材料只有一个。原材料标号为 1 到 N。做披萨很简单，只要把原材料混合好然后放进烤箱里烤一烤就行了。但 Geppetto 发现一共有M (0 <= M <= 400) 对原材料是冲突的，如果一对冲突的原材料混合在一份披萨里，这份披萨就会变得十分难吃。这给他带来了额外的麻烦。
Geppetto 想知道他最多能做多少种不同的比萨。如果一份比萨上有编号为 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
31
|
void solve()
{
int n,m;
cin >> n >> m;
vector<pii> clash(m);
for(int i=0;i<m;i++)
{
cin >> clash[i].first >> clash[i].second;
}
// 定义第i各二进制位数为1是选择第i种材料，否则是不选
int hi = (1 << n) - 1; // 最多有2^k-1中选择的状态
int cnt = 0; // 满足条件的种数
// 枚举所有的状态
for(int i=0;i<=hi;i++)
{
bool ans = true;
// 对每个状态枚举所有的冲突调料进行判断
for(int j=0;j<m;j++)
{
auto [x,y] = clash[j];
// 如果此状态下有任何一对冲突调料同时出现，则此状态下的披萨无法做出
if(i & (1 << (x-1)) and i & (1 << (y-1))) // -1切换下标为0 (n==20)
{
ans = false;
break;
}
}
if(ans) cnt++;
}
cout << cnt << endl;
}
|
我能赢吗？
在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。给定两个整数 num （整数池中可选择的最大数）和 need（累计和），若先出手的玩家能稳赢则返回 Yes ，否则返回 No 。假设两位玩家游戏时都表现 最佳 。
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
|
void solve()
{
int num,need;
cin >> num >> need;
if(need == 0)
{
cout << "Yes\n";
return;
}
int total = 0;
for(int i=1;i<=num;i++) total += i;
if(total < need)
{
cout << "No\n";
return;
}
// 总共有2^k种状态，0位默认不用(n<=15)
vector<int> dp(1<<(num+1));
//status:当前状态 rest:当前状态下还需要选的数字和
auto dfs = [&](auto &&self,int status,int rest) -> bool
{
if(rest <= 0) return false;// 表示上一个人赢了
if(dp[status] != 0) return dp[status] == true; // 记忆化搜索
// 否则尝试每一路径
bool ans = false;
for(int i=1;i<=num;i++)
{
// 当前位等于1可以走 且 走这一位后后手会输
if((status & (1ll << i)) != 0 && !self(self,(status ^ (1ll << i)),rest - i))
{
ans = true; // 代表当前选手会赢
break;
}
}
// 更新状态缓存表
dp[status] = ans ? 1 : -1;
return ans;
};
if(dfs(dfs,(1<<(num+1))-1,need))
{
cout << "Yes\n";
return;
}
cout << "No\n";
}
|
火柴拼正方形
你将得到一个整数数组 arr ，其中 arr[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能使这个正方形，则返回 Yes ，否则返回 No 。
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
|
void solve()
{
int n;
cin >> n;
vector<int> arr(n+1);
for(int i=1;i<=n;i++) cin >> arr[i];
int total = accumulate(arr.begin()+1,arr.end(),0);
if(total % 4 != 0)
{
cout << "No\n";
return;
}
int split = total / 4;
vector<int> dp(1<<(n+1));
auto dfs = [&](auto &&self,int status,int cursum,int restcnt) -> bool
{
if(restcnt == 0) return true; //如果剩余0条边未拼成，则说明能拼成
if(dp[status] != 0) return dp[status] == true;
//考察每一根火柴，只能使用状态为1的火柴
bool ans = false;
for(int i=1;i<=n;i++)
{
if((status & (1ll << i)) && cursum + arr[i] <= split)
{
// 如果刚好拼成则重置cursum待拼边数减一
if(cursum + arr[i] == split)
{
ans = self(self,status ^ (1ll << i),0ll,restcnt-1);
}
else
ans = self(self,status ^ (1ll << i),cursum + arr[i],restcnt);
if(ans) break;
}
}
dp[status] = ans ? 1 : -1;
return ans;
};
if(dfs(dfs,(1<<(n+1))-1,0,4))
cout << "Yes";
else cout << "No";
}
|
TSP问题
某乡有 n(2<= n<= 20) 个村庄，有一个售货员，他要到各个村庄去售货，各村庄之间的路程 s (0<s<1000) 是已知的，且 A 村到 B 村与 B 村到 A 村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为 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
36
37
38
39
40
41
42
43
44
45
|
// n == 20 的状压DP，接近于临界数据量，为了避免超时，应避免使用vector及stl优化常数时间
int getmin(int a,int b)
{
return a > b ? b : a;
}
int grid[N][N];
int dp[1<<N][N]; // dp[status][i] 表示在状态status下到达i村庄的最短路径是多少
int n;
// status : 比特位 为 1 : 代表当前标号的村庄已经走过 0 ：代表还没走过
// cur : 表示当前售货员停在哪个村庄
int dfs(int status,int cur)
{
if(status == (1 << n) - 1)
{
return grid[cur][0]; //此时代表所有村庄均已经过，仅需返回0起始村庄
}
if(dp[status][cur] != -1) // 记忆化搜索
{
return dp[status][cur];
}
int ans = INF;
for(int i=0;i<n;i++)
{
if((status & (1 << i)) == 0)
{
ans = getmin(ans,grid[cur][i] + dfs((status | (1 << i)),i));
}
}
dp[status][cur] = ans;
return ans;
}
void solve()
{
cin >> n;
memset(dp,-1,sizeof dp); // 初始化DP缓存表
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin >> grid[i][j];
}
}
// 初始状态00...0001代表此时在0号村庄
cout << dfs(1,0) << endl;
}
|
关灯问题II
$$
现有 n (1 <= n <= 10)盏灯，以及 m (1 <= m <= 100)个按钮。\每个按钮可以同时控制这 n 盏灯——按下了第 i 个按钮，对于所有的灯都有一个效果。按下 i 按钮对于第 j 盏灯，是下面 3 种效果之一：\
- 如果 a_{i,j} 为 1，那么当这盏灯开了的时候，把它关上，否则不管；\
- 如果 a_{i,j} 为 -1，如果这盏灯是关的，那么把它打开，否则也不管；\
- 如果 a_{i,j} 为 0，无论这灯是否开，都不管。\
现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。前两行两个整数，分别是 n 和 m。\
接下来 m 行，每行 n 个整数，第 (i+2) 行的第 j 个整数为 a_{i,j}，表示第 i 个开关对第 j 个灯的效果。
$$
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
|
void solve()
{
int n,m;
cin >> n >> m;
// con[i][j] 表示第i格按钮按下时对第j个灯的影响
vector<vector<int>> con(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin >> con[i][j];
}
}
// status : 表示灯目前的状态：1为亮，否则是灭
vector<int> dp(1<<n,-1); // dp[status]到达status状态最少需要按几次
int ans = INF;
auto dfs = [&](auto &&self,int status,int curcnt) -> void
{
if(status == 0) //如果都灭了则更新答案
{
ans = min(ans,curcnt);
return;
}
// 重要剪枝
if(curcnt >= ans) return;
if(dp[status] != -1 and dp[status] <= curcnt) return;
dp[status] = curcnt;
for(int i=1;i<=m;i++)
{
// nextsta表示按下第i个按钮后n盏灯变化后的状态
int nextsta = status;
for(int j=1;j<=n;j++)
{
// 将灯的下标-1转换为从0开始标号
if(con[i][j] == -1 and (nextsta & (1 << (j-1))) == 0)
{
nextsta |= (1 << (j-1));
}
if(con[i][j] == 1 and (nextsta & (1 << (j-1))) != 0) // != 0 !! 并非 == 1
{
nextsta ^= (1 << (j-1));
}
}
self(self,nextsta,curcnt + 1);
}
};
dfs(dfs,(1<<n)-1,0);
if(ans == INF)
{
cout << -1 << endl;
}
else
cout << ans << endl;
}
|
经典动态规划模型收集
位图解决背包方案问题
$$
你有一架天平和N 个砝码, 这 N 个砝码重量依次是 W_{1}, W_{2}, \cdots, W_{N} ~ 请你计算一共可以称出多少种不同的重量?
$$
01背包求方案数的模板题:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
const int N = 1e7+10;
const int M = 0;
bitset<N> dp;
void solve()
{
int n;
cin >> n;
int val[n+1];
for(int i=1;i<=n;i++) cin >> val[i];
dp[0] = 1;
for(int i=1;i<=n;i++)
{
dp |= dp << val[i];
//表示将dp向左边移动val[i]位后与原dp进行与或操作
}
for(int i=1;i<=n;i++)
{
//表示将dp向右边移动val[i]位后与原dp进行与或操作
dp |= dp >> val[i];
}
cout << dp.count()-1;
}
|
LIS最长上升子序列O(n*logn)
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
|
// 求两个排列的最长公共子序列 ， 即求下面POS数组的最长上升子序列
void solve()
{
int n;
cin >> n;
vector<int> a(n+1);
vector<int> mp(n+1); // mp[x]表示x值在a中的下标
for(int i=1;i<=n;i++) cin >> a[i],mp[a[i]] = i;
vector<int> pos; // b的数字在a中的下标位置
for(int i=1;i<=n;i++)
{
int x;
cin >> x;
pos.push_back(mp[x]);
}
vector<int> tail;// 目前所有长度为i的上升子序列的最小结尾数
for(auto x : pos)
{
auto it = lower_bound(tail.begin(),tail.end(),x);
if(it == tail.end())
{
tail.push_back(x);
}
else *it = x;
}
cout << tail.size() << endl;
}
|
LCS最长公共子序列O(n*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
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
|
void solve()
{
string s1,s2;
cin >> s1 >> s2;
int n = s1.size();
int m = s2.size();
s1 = "#" + s1;
s2 = "@" + s2;
int dp[n+1][m+1];//代表长度为i的s1对应到长度为j的s2上所能产生的最长公共子序列长度。
//注意边界情况:
for(int i=0;i<=n;i++) dp[i][0] = 0;
for(int j=0;j<=m;j++) dp[0][j] = 0;
for(int len1 = 1;len1<=n;len1++)
{
for(int len2 = 1;len2<=m;len2++)
{
if(s1[len1]==s2[len2])
{
dp[len1][len2] = dp[len1-1][len2-1] + 1;
}
else
dp[len1][len2] = max(dp[len1-1][len2],dp[len1][len2-1]);
}
}
cout << dp[n][m];
}
//滚动数组一维空间优化
void solvepromoted()
{
string s1,s2;
cin >> s1 >> s2;
int n = s1.size();
int m = s2.size();
s1 = "#" + s1;
s2 = "@" + s2;
int dp[m+1];
int backup,leftup;
//初始化dp[0][j]
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)
{
//dp[i][0]
leftup = 0;
for(int j=1;j<=m;j++)
{
backup = dp[j];
if(s1[i]==s2[j])
{
dp[j] = leftup + 1;
}
else
{
dp[j] = max(dp[j-1],dp[j]);
}
leftup = backup;
}
}
cout << dp[m];
}
|
基于子串或子数组的计数DP
套路题，常常定义dp[i]为以1 ~ i为左端点，i为右端点的所有字串中，满足条件的数量，ans就是总的dp数组之和
例：美丽字符串计数
当一个由0和1组成的非空字符串SS满足以下条件时，我们称其为美丽字符串：
(条件) 可以通过以下操作序列将S的长度缩减至1，并使S中最终剩下的唯一字符是1
-
选择任意满足1≤i≤∣S∣−1的整数i。
-
按以下规则定义整数x：
S_i == S_(i+1) -> x = 1
else x = 0
-
移除S_i和S_(i+1)，并在原位置插入与x对应的数字。
给定一个长度为N、由0和1组成的字符串T。
请统计T的所有子串中美丽字符串的数量。即使两个子串内容相同，只要在原串中的位置不同，就视为不同的子串。
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()
{
int n;
cin >> n;
string s;
cin >> s;
s = "%" + s;
vector<int> dp(n+5); // dp[i]表示每个1~i每个下标到i构成的子串中美丽字符串的总和
int ans = 0;
dp[1] = (s[1] == '1');
ans += dp[1];
for(int i=2;i<=n;i++)
{
// 之前是完美字符串的个数加上这个1还是原来的完美字符串个数
// 但需要单独加上i单独拿出来时的1长度
if(s[i] == '1') dp[i] = dp[i-1] + 1;
// 之前不是完美字符串的字串在添上这个0后会变成完美字符串
else dp[i] = (i - 1) - dp[i-1];
// 累加贡献
ans += dp[i];
}
cout << ans << endl;
}
|
换根DP
树上的某些问题，需要知道以不同节点做根的情况下，答案是多少
换根DP的重要思考点：
如果已经得到父节点做根的答案，怎么加工得到子节点做根的答案，就是所谓的换根，为了达成换根这个目标，可能需要设置若干额外的信息来帮助计算
换根DP的过程：
- 先以节点1为头进行树的遍历，收集信息，dfs1过程
- 得到1节点作为根的答案，然后从1节点开始再进行树的遍历，求解每个节点做根的答案，dfs2过程
核心在于换根时，答案如何转移
推导状态转移方程时，可以画一个简单的完全二叉树结构继续进行模拟推导
以某个节点为根的最大深度和
给定一个 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
// 省略建图过程
vector<int> dp(n+1); // 以i节点为根，所能得到的深度和
vector<int> sum(n+1); // 以1节点为根，到所有节点的距离和
vector<int> size(n+1); // 以1节点为根，第i节点的子树的大小
auto dfs1 = [&](auto &&self,int u,int fa) -> void
{
// 先递归到叶子节点
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{
self(self,v,u);
}
}
// 在叶子节点初始化
size[u] = 1;
sum[u] = 0;
// 递归上升至根节点，在叶子节点时不会进行下述操作
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{
size[u] += size[v];
sum[u] += sum[v] + size[v];
}
}
};
auto dfs2 = [&](auto &&self,int u,int fa) -> void
{
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{
dp[v] = dp[u] - size[v] + n - size[v]; // 换根状态转移
self(self,v,u);
}
}
};
dfs1(dfs1,1,-1);
// sum数组的实际作用其实就是为了提供sum[1]进行状态转移
dp[1] = sum[1];
dfs2(dfs2,1,-1);
auto it = max_element(dp.begin()+1,dp.end());
cout << it - dp.begin() << endl;
}
|
Tree Painting
给定一棵包含 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
28
29
30
31
32
33
34
35
36
37
38
39
|
// 省略建图过程
vector<int> dp(n+1); // 以i节点为根开始染色，所能得到的最大收益
vector<int> rootval(n+1); // 递归获取以1节点为根，能获得的最大收益
vector<int> size(n+1); // 以1节点为根，第i节点的子树的大小
auto dfs1 = [&](auto &&self,int u,int fa) -> void
{
size[u] = 1;
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{
self(self,v,u);
size[u] += size[v];
rootval[u] += rootval[v];
}
}
rootval[u] += size[u]; // 加上第一次染色时获得的相当于自己子树大小的收益
};
// dp[i] 节点i作为整棵树最先染的点，染完整棵树后，收益是多少
auto dfs2 = [&](auto &&self,int u,int fa) -> void
{
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{ // 换到此根增加的贡献 减少的贡献
dp[v] = dp[u] + n - size[v] - size[v]; // 换根状态转移
self(self,v,u);
}
}
};
dfs1(dfs1,1,-1);
dp[1] = rootval[1]; // 转移前需要获取以1节点为根时所能获得的最大收益
dfs2(dfs2,1,-1);
auto it = max_element(dp.begin()+1,dp.end());
cout << *it << endl;
}
|
Tree with Maximum Cost
给定一棵恰好有 n 个顶点的树。树是一个连通无向图，包含 $n-1$ 条边。树上的每个顶点 $v$ 都被赋予了一个值 $a_v$。
定义 dist(x, y) 为顶点 x 和 y 之间的距离，即它们之间简单路径上的边数。
我们将树的代价定义如下：首先，固定树上的某个顶点 v$。然后，树的代价为
$$
\sum\limits_{i = 1}^{n} dist(i, v) \cdot a_i
$$
你的任务是计算，如果可以任意选择 v，树的最大可能代价是多少。
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
|
void solve()
{
// ... 省略读入建边操作
vector<int> dp(n+1);
vector<int> sum(n+1);
vector<int> rootval(n+1);
vector<int> size(n+1);
auto dfs1 = [&](auto &&self,int u,int fa) -> void
{
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{
self(self,v,u);
}
}
size[u] = 1;
sum[u] = arr[u];
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{
sum[u] += sum[v];
size[u] += size[v];
rootval[u] += rootval[v] + sum[v];
}
}
};
dfs1(dfs1,1,-1);
dp[1] = rootval[1]; // 仅需要一个结果
auto dfs2 = [&](auto &&self,int u,int fa) -> void
{
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{ // 根据转移方程换根得到所有答案
dp[v] = dp[u] - sum[v] + sum[1] - sum[v];
self(self,v,u);
}
}
};
dfs2(dfs2,1,-1);
int ans = *max_element(dp.begin()+1,dp.end());
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T;
#ifdef Single
T = 1;
#else
cin >> T;
#endif
while(T--)
{
solve();
}
return 0;
}
|
Choosing Capital for Treeland
Treeland 国有 n 个城市，有些城市间存在 单向 道路。这个国家一共有 n - 1 条路。我们知道，如果把边视作双向的，那么从任意城市出发能到达任意城市。
城市的委员会最近决定为 Treeland 国选择一个首都，显然首都会是国中的一个城市。委员会将在首都开会，并经常去其他城市（这里不考虑从其他城市回到首都）。因此，如果城市 a 被选为首都，那么所有的道路应该被定向，以使得我们能从城市 a 到达其他城市。所以，有些路可能需要反转方向。
帮助委员会选择首都使得他们需要反转道路的次数最小。
第一行输出需要反转的道路数量的最小值。第二行输出所有可能的选择首都的方式，你需要以从小到大的顺序输出所有可能的城市编号。
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
|
// ...部分建边过程省略
for(int i=1;i<n;i++)
{
int u,v;
cin >> u >> v;
add(u,v,0);
add(v,u,1);
}
vector<int> dp(n+1);
vector<int> rev(n+1); // 求解rootval
auto dfs1 = [&](auto &&self,int u,int fa) -> void
{
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
int w = edge[i].w;
if(v != fa)
{
self(self,v,u);
rev[u] += rev[v] + w;
}
}
};
dfs1(dfs1,1,-1);
dp[1] = rev[1];
auto dfs2 = [&](auto &&self,int u,int fa) -> void
{
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
int w = edge[i].w;
if(v != fa)
{
if(w == 0) // 正向
{
dp[v] = dp[u] + 1;
}
else // 反向
{
dp[v] = dp[u] - 1;
}
self(self,v,u);
}
}
};
dfs2(dfs2,1,-1);
int ans = *min_element(dp.begin()+1,dp.end());
cout << ans << endl;
for(int i=1;i<=n;i++)
{
if(ans == dp[i]) cout << i << ' ';
}
}
|
Nearby Cows G
FJ 注意到了他的奶牛经常在附近的田地移动。考虑到这个事情，他想要在每个田地里种足够的草，不仅是为了最初在那块地里的奶牛，也是为了从附近田地来的奶牛。
特别地，FJ 的农场由 N(1 <= N <=100000) 个田地组成，某些田地之间由双向道路连接（一共有 N-1 条）。对于田地 i，它是 C_i 头奶牛的家，尽管奶牛有时能经过最多 K 条边去到其它田地。
FJ 想在任意一个田地 i中种足够的草去喂养最大数量的奶牛 M_i（最终可能到这块地的奶牛），即仅经过最多 K(1 <= K <= 20) 条边到达这里的奶牛。给定农场的结构和任意一个田地的奶牛数量 C_i，请求出对于任意一个 i 求出对应的 M_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
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
|
// ...省略读入n与k及边的过程
vector<vector<int>> dp(n+1,vector<int>(k+1)); // dp[u][i] 表示以u为根节点向外扩展i节点到的节点权值和
vector<vector<int>> sum(n+1,vector<int>(k+1)); // sum[u][i] : 以u为头的子树内，距离为i的节点权值和
for(int i=1;i<=n;i++) cin >> sum[i][0];
auto dfs1 = [&](auto &&self,int u,int fa) -> void
{
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{
self(self,v,u);
}
}
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{
for(int j=1;j<=k;j++)
{
sum[u][j] += sum[v][j-1];
}
}
}
};
auto dfs2 = [&](auto &&self,int u,int fa) -> void
{
for(int i=head[u];i;i=edge[i].next)
{
int v = edge[i].to;
if(v != fa)
{
dp[v][0] = sum[v][0];
dp[v][1] = sum[v][1] + dp[u][0];
for(int j=2;j<=k;j++)
{
dp[v][j] = sum[v][j] + dp[u][j-1] - sum[v][j-2];
}
self(self,v,u);
}
}
};
dfs1(dfs1,1,-1);
for(int i=0;i<=k;i++) dp[1][i] = sum[1][i];
dfs2(dfs2,1,-1);
for(int i=1;i<=n;i++)
{
int ans = 0;
for(int j=0;j<=k;j++)
{
ans += dp[i][j];
}
cout << ans << endl;
}
}
|