DP

DP真是做到自闭，除了第一题，其它都是连蒙带猜，状压dp有些熟悉，H题的简单DP也想不到，果然DP和数论是魔鬼。

  • 状态压缩DP
  • 树形DP
  • 简单DP
  • 拓扑排序

A. QAQ

 

对于Q，若有QA个数大于0，则ans加QA的个数，Q的个数加一，对于A，若Q的个数大于0，则QA的个数加上Q的个数。

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
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string s;
int main() {
	cin >> s;
	int len = s.length();
	int ans = 0;
	int qa = 0;
	int q = 0;
	for (int i = 0; i < len; i ++ ) {
		if (s[i] == 'Q') {
			if (qa == 0)q ++ ;
			else {
				ans += qa;
				q++;
			}
		}
		else if (s[i] == 'A') {
			qa += q;
		}
	}
	cout << ans << endl;
	return 0;
}

 

B. The least round way

 

maze中的数大于等于0，等于0时是特殊情况。

只有在相乘的数中有因数2，5才会产生乘积末尾的0，因此因数2，5的个数是影响因素。

则我们记录每个数字包含2，5的个数，分开记录。

考虑一下，一条路径上最终乘积中末尾0的个数一定等于路径上包含因数2与因数5中小的那个。即cnt(10)=min(cnt(2),cnt(5))。所以我们要找的就是包含因数2最少的路径与包含因数5最少的路径，并比较两者，取小的那个。

至于输出路径，同样是分开记录2和5，path[i] [j]记录坐标(i,j)的前一个坐标，(i,j)的父节点，最后递归输出。

以上是maze中不含0的情况，若maze中含0，则比较以上得到的结果ans是否大于1，若大于1，则还不如直接经过0。所以若ans大于1，只要找到任意一条经过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
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1005;
int n;
int maze[maxn][maxn][2];
int dp[maxn][maxn][2];
int path[2][maxn][maxn][2];
int num_2(int x) {
	int res = 0;
	while (x%2==0) {
		x = x / 2;
		res++;
	}
	return res;
}
int num_5(int x) {
	int res = 0;
	while (x % 5 == 0) {
		x = x / 5;
		res++;
	}
	return res;
}
void print(int k, int i, int j) {
	if (i == 1 && j == 1) {
		return;
	}
	int x = path[k][i][j][0], y = path[k][i][j][1];
	print(k, x, y);
	if (x == i - 1)cout << 'D';
	else cout << 'R';
}
int main() {
	cin.sync_with_stdio(false);
	int a = -1, b = -1;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int tp;
			cin >> tp;
			if (tp == 0) {
				a = i, b = j;
				continue;
			}
			maze[i][j][0] = num_2(tp);//0记录因数2
			maze[i][j][1] = num_5(tp);//1记录因数5，下同
		}
	}
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	dp[1][1][0] = maze[1][1][0];
	dp[1][1][1] = maze[1][1][1];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k <= 1; k++) {
				if (i > 1 && dp[i][j][k] > dp[i - 1][j][k] + maze[i][j][k]) {
					dp[i][j][k] = dp[i - 1][j][k] + maze[i][j][k];
					path[k][i][j][0] = i - 1; path[k][i][j][1] = j;
				}
				if (j > 1 && dp[i][j][k] > dp[i][j - 1][k] + maze[i][j][k]) {
					dp[i][j][k] = dp[i][j - 1][k] + maze[i][j][k];
					path[k][i][j][0] = i; path[k][i][j][1] = j - 1;
				}
			}
		}
	}
	int ans = min(dp[n][n][0], dp[n][n][1]);
	if (ans > 1 && a != -1 && b != -1) {
		cout << 1 << endl;
		for (int i = 1; i < a; i++) {
			cout << 'D';
		}
		for (int i = 1; i < n; i++) {
			cout << 'R';
		}
		for (int i = a; i < n; i++) {
			cout << 'D';
		}
	}
	else {
		cout << ans << endl;
		if (dp[n][n][0] < dp[n][n][1]) {
			print(0, n, n);
		}
		else
		{
			print(1, n, n);
		}
	}
	return 0;
}

 

C. A Simple Task

 

状态压缩DP

对于一个集合，若新加入的点等于该集合的起始点，则出现了环。

注意：

  • 由于未设置访问标记，故有1->2->1的情况，ans应减去边数。

  • 同样，由于无访问标记，同一个环1->2->3->1，1->3->2->1，会被正反计算，计算两次，故ans还应除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
47
48
#include<iostream>
using namespace std;
#define ll long long
int G[20][20];
ll n, m, ans;
ll lowest(ll s) {
	int t = (s&-s);
	ll res = 1;
	while ((t & 1) == 0) {
		t =t>>1;
		res++;
	}
	return res;
}
ll dp[(1 << 20)][20];
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		G[u][v] = G[v][u] = 1;
	}
	for (int i = 1; i <= n; i++) {
		dp[(1 << (i - 1))][i] = 1;
	}
	ll mx = (1 << n) - 1;
	for (ll s = 1; s <= mx; s++) {
		for (int now = 1; now <= n; now++) {
			if (dp[s][now] == 0)continue;
			ll st = lowest(s);
			for (int nex = st; nex <= n; nex++) {
				if ((now != nex) && G[now][nex]) {
					if ((s&(1 << (nex - 1)) && (nex == st))) {
						ans += dp[s][now];
					}
					else if (!(s&(1 << (nex - 1)))) {
						ll ss = s | (1 << (nex - 1));
						dp[ss][nex] += dp[s][now];
					}
				}
			}
		}
	}
	ans -= m;
	ans /= 2;
	cout << ans << endl;
	return 0;
}

 

D. k-Tree

树形DP

但还看到一种更巧妙的做法。

题目要求我们用至少一个大于等于d的数字凑出n，限制条件较麻烦，因此正的不行，反的来，我们只用小于d的数字凑出n，则k树变成了（d-1）树，同时计算出k树在无限制条件下凑出n的方法数，两者相减即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
int n, k, d;
long long dpa[105], dpb[105];
const int md = 1e9 + 7;
int main() {
	cin >> n >> k >> d;
	dpa[0] = 1;
	dpb[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k&&(i-j>=0); j++) {
			dpa[i] = (dpa[i] + dpa[i - j]) % md;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= d-1 && (i - j >= 0); j++) {
			dpb[i] = (dpb[i] + dpb[i - j]) % md;
		}
	}
	long long ans = (dpa[n] - dpb[n]+md)%md;
	cout << ans;
	return 0;
}

 

E. Choosing Capital for Treeland

 

树形DP，一边深搜一边记录

两个DFS函数，dfs1(i)记录以 i 为根时，要改变的边数；dfs2(i)记录以 i 为首都时要改变的边数，即答案集合。注意这两者是不同的！！

dfs1(root,-1)是因为要将图转化为树，以便进行树形DP；dfs2(root,-1)才是产生最终答案集合。

dfs1的结果中只有dp[root]有用，作为下一步从根到叶更新的基础；dfs2的结果中所有都有用。

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
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 2e5 + 5;
int n, dp[maxn], ans[maxn];
struct Edge
{
	int to;
	int is_pos;
};
vector<Edge>e[maxn];
void add_edge(int u, int v) {
	e[u].push_back({ v,1 });
	e[v].push_back({ u,0 });
}
void dfs1(int now, int pre) {
	for (int i = 0; i < e[now].size(); i++) {
		int to = e[now][i].to;
		int flg = e[now][i].is_pos;
		if (to == pre)
			continue;
		dfs1(to, now);
		if (flg == 1)dp[now] += dp[to];
		else dp[now] += (dp[to] + 1);
	}
}
void dfs2(int now, int pre) {
	for (int i = 0; i < e[now].size(); i++) {
		int to = e[now][i].to;
		int flg = e[now][i].is_pos;
		if (to == pre)
			continue;
		if (flg == 1)ans[to] = ans[now] + 1;
		else ans[to] = ans[now] - 1;
		dfs2(to, now);
	}
}
int main() {
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		add_edge(u, v);
	}
	int root = 1; //规定以root为根，可以改变root，只要在n范围内
	dfs1(root, -1);//从下到上更新
	ans[root] = dp[root];
	dfs2(root, -1);//从上到下更新
	vector<int>res;
	int min = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++) {
		if (ans[i] < min) {
			min = ans[i];
			res.clear();
			res.push_back(i);
		}
		else if (ans[i] == min)
			res.push_back(i);
	}
	cout << min << endl;
	for (auto c : res) {
		cout << c << ' ';
	}
	return 0;
}

 

G. Substring

 

拓扑排序+图上dp

对于每一个为起点的点，深搜至叶子，状态转移为：该点=max（各子节点）+1

判环和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
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
73
74
75
76
77
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 3e5 + 5;
int n, m;
string s;
int vis[maxn];
int dp[maxn][30];
bool flg = 1;
bool is_root[maxn];
int fat[maxn];
struct Node
{
	char val;
	vector<int>to;
}nd[maxn];
void findring(int p) {
	vis[p] = 1;
	for (auto i : nd[p].to) {
		if (!vis[i])findring(i);
		else if (vis[i] == 1) {
			cout << -1;
			exit(0);
		}
	}
	vis[p] = 2;
}
void solve(int p) {
	vis[p] = 1;
	for (auto i : nd[p].to) {
		if (!vis[i]) {
			solve(i);
		}
	}
	if (nd[p].to.size() != 0) {
		for (auto i : nd[p].to) {
			for (int j = 0; j < 26; j++) {
				dp[p][j] = max(dp[p][j], dp[i][j]);
			}
		}
	}
	dp[p][nd[p].val - 'a']++;
}
int main() {
 
	cin >> n >> m;
	memset(is_root, 1, n+5);
	for (int i = 1; i <= n; i++) {
		cin >> nd[i].val;
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		nd[u].to.push_back(v);
		is_root[v] = 0;
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i])findring(i);
	}
	int ans = 0;
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++) {
		if (!vis[i])solve(i);
	}
	for (int i = 1; i <= n; i++) {
		if (is_root[i]) {
			for (int j = 0; j < 26; j++) {
				ans = max(dp[i][j], ans);
			}
		}
	}
	cout << ans;
	return 0;
}

 

H. Beautiful Array

 

建立3个DP，dp0记录最大字段和，dp1记录 i 之前的最大字段和+a[i]*x，dp2记录假设 i 不在要乘以x的区间中时，即区间已经乘完了时，当前的最大字段和。

最终答案取dp2最大值。

将一段区间乘上 x ，使数组的最大字段和最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x,y;
ll dp[10],ans;
int main(){
    scanf("%lld%lld",&n,&x);
    for(int i=1;i<=n;i++){
        scanf("%lld",&y);
        dp[0]=max(0LL,dp[0]+y);
        dp[1]=max(dp[0],dp[1]+y*x);
        dp[2]=max(dp[1],dp[2]+y);
        ans=max(ans,dp[2]);
    }
    printf("%lld\n",ans);
    return 0;
}

 

K. Shaass and Bookshelf

 

厚度为1和为2的分开记录，再分别按照宽度排序，接下来就是要确定垂直放的有几本厚度为1的，有几本厚度为2的，两层循环，1的本书，2的本书，若水平放置的总宽度小于垂直放置的总厚度，则可行，比较大小。

似乎除了开始的前缀和数组，并未用到dp，看到有一个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
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 150;
int n;
int c1[maxn], c2[maxn];
int sum1[maxn], sum2[maxn];
int n1, n2;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		if (a == 1) {
			c1[++n1] = b;
		}
		else {
			c2[++n2] = b;
		}
	}
	sort(c1+1,c1+n1+1);
	sort(c2+1,c2+n2+1);
	for (int i = 1; i <= n1; i++) {
		sum1[i] = sum1[i - 1] + c1[i];
	}
	for (int i = 1; i <= n2; i++) {
		sum2[i] = sum2[i - 1] + c2[i];
	}
	int ans = 0x3f3f3f3f;
	for (int i = 0; i <= n1; i++) {
		for (int j = 0; j <= n2; j++) {
			int down = i + 2 * j;
			int up = sum1[n1 - i] + sum2[n2 - j];
			if (up <= down) {
				ans = min(ans, down);
			}
		}
	}
	cout << ans;
	return 0;
}

 

看到的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
29
#include <bits/stdc++.h>
#define N 200005
using namespace std;
 
int f[101][203] = {0};
int val[101], w[101], V = 0;
 
int main()
{
    int n, i, j, thick, wid;
    scanf("%d",&n);
    for(i = 1; i <= n; i++)
    {
        scanf("%d %d",&thick, &wid);
        val[i] = thick;
        w[i] = thick + wid;
        V += thick;
    }
 
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= V; j++)
        {
            if (j < w[i]) f[i][j] = f[i-1][j];
            else f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + val[i]);
        }
    }
    printf("%d\n", V-f[n][V]);
}