题意
模板题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
const int N=310,INF=0x3f3f3f3f;
int s[N],a[N],n,f[N][N];
int main(){
cin>>n;
memset(f,0x3f,sizeof f);
for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i],f[i][i]=0;
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
for(int k=l;k<r;k++){
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
}
}
}
cout<<f[1][n];
}
|
技巧总结：注意先循环阶段，再状态，最后决策。因为更新状态要用到上一个阶段的状态。
题意
游戏开始时，给定玩家一个具有 N 个顶点 N 条边的多边形，每个点都有自己的权值
每个顶点上写有一个整数，每个边上标有一个运算符 +（加号）或运算符 *（乘号）。
每次可以删除一条边，合并相邻两个点，按照边的运算符，得到新的点
最后剩下的点的值最多是多少
N<=50
思考
小技巧
处理环的问题，一般不用枚举第一次断开的点。而是任选一个点断开，再在后面接上相同长度的线段。
这样任意一种第一次断开的情况，都在这个新的线段上。
状态：f[l][r]最大值，g[l][r]最小值
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
| #include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110, INF = 32768;
int n;
int w[N];
char c[N];
int f[N][N], g[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> c[i] >> w[i];
c[i + n] = c[i];
w[i + n] = w[i];
}
for (int len = 1; len <= n; len ++ )
for (int l = 1; l + len - 1 <= n * 2; l ++ )
{
int r = l + len - 1;
if (len == 1) f[l][r] = g[l][r] = w[l];
else
{
f[l][r] = -INF, g[l][r] = INF;
for (int k = l; k < r; k ++ )
{
char op = c[k + 1];
int minl = g[l][k], minr = g[k + 1][r];
int maxl = f[l][k], maxr = f[k + 1][r];
if (op == 't')
{
f[l][r] = max(f[l][r], maxl + maxr);
g[l][r] = min(g[l][r], minl + minr);
}
else
{
int x1 = maxl * maxr, x2 = maxl * minr, x3 = minl * maxr, x4 = minl * minr;
f[l][r] = max(f[l][r], max(max(x1, x2), max(x3, x4)));
g[l][r] = min(g[l][r], min(min(x1, x2), min(x3, x4)));
}
}
}
}
int res = -INF;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i][i + n - 1]);
cout << res << endl;
for (int i = 1; i <= n; i ++ )
if (res == f[i][i + n - 1])
cout << i << ' ';
return 0;
}
|
技巧总结：注意最小值和最大值都要存下
题意
Ural 大学有 N名职员，编号为 1∼N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤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
| #include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 60010, INF = 32768;
int n,a[N];
vector<int> mp[N];
int f[N][2];
bool st[N];
void dfs(int u){
for(int tp:mp[u]){
dfs(tp);
f[u][0]+=max(f[tp][0],f[tp][1]);
f[u][1]+=f[tp][0];
}
f[u][1]+=a[u];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int k,l;
for(int i=1;i<n;i++){
scanf("%d%d",&l,&k);
mp[k].push_back(l);
st[l]=true;
}
int root = 1;
while (st[root]) root ++ ;
dfs(root);
cout<<max(f[root][0],f[root][1]);
return 0;
}
|
技巧总结：dfs在最后记得加上a[u]
题意
有依赖的背包
思考
经典树形DP问题，f[i][j]表示当前在i节点，并且当前已经选的课数量是j，的最大学分数量
难点在于对dfs的理解，这里处理到每一层的时候，直接对每一个子节点进行递归，但实际求解是一个回溯的过程，分组背包的方式也与经典分组背包不同，这里基于闫氏dp的思想，以集合为概念，就可以将每组子节点分开来求了，用每一组子节点的每一个状态来处理当前节点每一种选课不同数量集合的方式。
这里有一些小点，我们新建虚拟节点0，其学分为0，这样可以将森林转化为树，然后在一个dfs里面处理完毕，同时选了一个学分为0点空节点，我们的总选课上限也要加一，在后面的便利过程中，每一次处理完当前节点的左右子节点后，需要在for外面将自己本身加上，保证了数据的完整性，在题目所有的循环中，要注意0这个边界，当当前节点的选课数量为0时是没有意义的，所以需要初始化为0，但是其本身就是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
| #include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 310;
int n, m;
vector<int> mp[N];
int w[N];
int f[N][N];
void dfs(int u)
{
for(int tp:mp[u]){
dfs(tp);
for (int j = m - 1; j >= 0; j -- )
for (int k = 1; k <= j; k ++ )
f[u][j] = max(f[u][j], f[u][j - k] + f[tp][k]);
}
for (int i = m; i; i -- ) f[u][i] = f[u][i - 1] + w[u];
f[u][0] = 0;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
scanf("%d%d",&x,&w[i]);
mp[x].push_back(i);
}
m++;
dfs(0);
cout<<f[0][m];
return 0;
}
|
技巧总结：dfs(son)相当于把前序状态更新了，再枚举当前状态，决策。
题意
给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。
请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。
思考
这是一道很好的树形dp题，即用到了用子节点更新父节点信息的普遍情况，又用到了用父节点更新子节点的情况，所以掌握这一道题是很有必要的。
首先分析题目，其实是要我们把每一个点到其他点的最长距离求出来，再求一个其中最短的就可以了，我们来分析一下每一个点可以再树上怎么走，其实就是向上和向下走
我们用 d1[u],d2[u],up[u],p1[u],p2[u]分别存一下需要的信息，这些数据存的是：
d1[u]：存下u节点向下走的最长路径的长度
d2[u]：存下u节点向下走的第二长的路径的长度
p1[u]：存下u节点向下走的最长路径是从哪一个节点下去的
p2[u]：存下u节点向下走的第二长的路径是从哪一个节点走下去的
up[u]：存下u节点向上走的最长路径的长度
u向下走是很容易的，dfs就可以了，那怎么向上走呢？其实向上走就是求一个点的父节点的不走该节点的最长路径，其实我们知道了每一个节点向下走的长度就可以知道向上的最长路径了，一个子节点 j 的向上最长路径就是 它的父节点 u 的最长向上路径和最长向下路径取最大值，如果向下最长路径经过了 j 就改为第二长的向下路径，对应代码：
1
2
| if(p1[u]==j)up[j]=max(up[u],d2[u])+w[i];
else up[j]=max(up[u],d1[u])+w[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
57
58
59
60
61
62
63
64
| #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f,N=10010;
int up[N],d1[N],d2[N],p1[N];
vector<PII> mp[N];
int n;
int dfs_d(int u,int fa){
d1[u]=d2[u]=-INF;
for(PII tp:mp[u]){
int diss=tp.first,ne=tp.second;
if(ne==fa) continue;
int val=dfs_d(ne,u)+diss;
if(val>d1[u]){
d2[u]=d1[u];
d1[u]=val;
p1[u]=ne;
}else if(val>=d2[u]){
d2[u]=val;
}
}
if(d1[u]==-INF) d1[u]=d2[u]=0;
return d1[u];
}
void dfs_u(int u,int fa){
for(PII tp:mp[u]){
int diss=tp.first,ne=tp.second;
if(ne==fa) continue;
if(p1[u]==ne){
up[ne]=max(d2[u],up[u])+diss;
}else{
up[ne]=max(d1[u],up[u])+diss;
}
dfs_u(ne,u);
}
}
int main(){
scanf("%d",&n);
int a,b,c;
for(int i=1;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
mp[a].push_back({c,b});
mp[b].push_back({c,a});
}
dfs_d(1,-1);
dfs_u(1,-1);
int ans=INF;
for(int i=1;i<=n;i++){
ans = min(ans,max(d1[i],up[i]));
}
cout<<ans;
return 0;
}
|
技巧总结：注意两次递归调用顺序。
题意
思考
