S+2 DP
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
int n, m, a, b;
int mark[1 << MAX], idx[1 << MAX];
bool DP[1 << MAX];
signed main() {
IOS;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
--a, --b;
mark[a] |= (1 << b);
mark[b] |= (1 << a);
}
DP[0] = 1;
for (int i = 1; i <= n; i++) {
idx[1 << i] = i;
}
for(int i = 1; i < (1 << n); i++) {
int ind = i ^ (i & (-i)), tmp = (i & (-i));
if (DP[ind] && ((ind & mark[idx[tmp]]) == 0)) {
DP[i] = 1;
}
}
ll ans = 0;
for (int i = 0; i < (1 << n); i++) {
ans += DP[i];
}
cout << ans << endl;
return 0;
}
B. 罪犯分组
- sum提前预处理出这个状态的的冲突数量，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
30const int MAX = (1 << 20);
int n, m, k, x, y, sum[MAX], DP[MAX];
signed main() {
IOS;
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
x--, y--;
for (int i = 1; i < (1 << n); i++) {
if ((i & (1 << x)) && (i & (1 << y))) {
sum[i]++;
}
}
}
memset(DP, 127, sizeof(DP));
DP[0] = 0;
for (int i = 0; i < (1 << n); i++) {
int s = (1 << n) - i - 1;
for (int j = s; j > 0; j = (j - 1) & s) {
if (sum[j] <= k) {
DP[i | j] = min(DP[i | j], DP[i] + 1);
}
}
}
cout << DP[(1 << n) - 1] << endl;
return 0;
}
C 牛塔
- 用状态表示当前状态的牛能承受的最大压力
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
37const int MAXN = 25, MAXM = (1 << 21) + 5;
int n, h[MAXN], w[MAXN], s[MAXN], DP[MAXM];
int ans;
int check(int x) {
int res = 0;
for (int i = 0; i < n; i++) {
if (x & (1 << i)) {
res += h[i];
}
}
return res;
}
signed main() {
IOS;
int H;
cin >> n >> H;
for (int i = 0; i < n; i++) {
cin >> h[i] >> w[i] >> s[i];
}
DP[0] = 1e9 + 7;
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if (!(i & (1 << j)) && DP[i] >= w[j]) {
DP[i | (1 << j)] = max(DP[i | (1 << j)], min(DP[i] - w[j], s[j]));
}
}
if (check(i) >= H) {
ans = max(ans, DP[i]);
}
}
if (ans == 0) {
cout << "Mark is too tall" << endl;
} else {
cout << ans << endl;
}
return 0;
}
D 区间回文
- 采用集合的方法进行；回文直接暴力就好了
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
int DP[MAX][MAX], JD[MAX][MAX];
string s;
signed main() {
IOS;
cin >> s;
s = ' ' + s;
int len = s.size() - 1;
for (int i = 1; i <= len; i++) {
for (int j = 1; j + i - 1 <= len; j++) {
int l = j, r = j + i - 1;
if (s[l] != s[r]) continue;
if (r - l <= 1 || JD[l + 1][r - 1]) {
JD[l][r] = 1;
}
}
}
for (int i = 1; i <= len; i++) DP[i][i] = 1;
for (int i = 2; i <= len; i++) {
for (int j = 1; j + i - 1 <= len; j++) {
int l = j, r = j + i - 1;
DP[l][r] = DP[l + 1][r] + DP[l][r - 1] - DP[l + 1][r - 1] + JD[l][r];
}
}
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
cout << DP[l][r] << endl;
}
return 0;
}
E. 括号构造
- DP[l][r] 的最小长度， DP[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
42int DP[MAX][MAX];
string MK[MAX][MAX];
string SL(char x) {
if (x == '(' || x == ')') {
return "()";
} else {
return "[]";
}
}
string s;
signed main() {
IOS;
cin >> s;
int n = s.size();
s = ' ' + s;
for (int i = 1; i <= n; i++) {
DP[i][i] = 1;
MK[i][i] = SL(s[i]);
}
for (int len = 1; len < n; len++) {
for (int l = 1; l + len <= n; l++) {
int r = l + len;
DP[l][r] = 1e9;
if ((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']')) {
DP[l][r] = DP[l + 1][r - 1];
MK[l][r] = s[l] + MK[l + 1][r - 1] + s[r];
} else {
DP[l][r] = DP[l + 1][r - 1] + 2;
MK[l][r] = SL(s[l]) + MK[l + 1][r - 1] + SL(s[r]);
}
for (int i = l; i < r; i++) {
if (DP[l][r] > DP[l][i] + DP[i + 1][r]) {
DP[l][r] = DP[l][i] + DP[i + 1][r];
MK[l][r] = MK[l][i] + MK[i + 1][r];
}
}
}
}
cout << MK[1][n] << endl;
return 0;
}
F. 深度之和最大
- 最简单的换根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
int DP[MAX], sz[MAX];
vector<int> G[MAX];
int n, ans = 1;
void dfs1(int u, int fa) {
sz[u] = 1;
for (auto v : G[u]) {
if (v == fa) continue;
dfs1(v, u);
sz[u] += sz[v];
}
DP[1] += sz[u];
}
void dfs2(int u, int fa) {
if (u != 1) {
DP[u] = DP[fa] - sz[u] + n - sz[u];
}
for (auto v : G[u]) {
if (v == fa) continue;
dfs2(v, u);
}
if (DP[u] > DP[ans]) {
ans = u;
}
}
signed main() {
IOS;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v), G[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 0);
cout << ans << endl;
return 0;
}
G. 选课
- 最基础的树形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
int DP[MAX][MAX];
vector<int> G[MAX];
int n, m;
void dfs(int u) {
for (int v : G[u]) {
dfs(v);
for (int i = m + 1; i > 1; i--) {
for (int j = 0; j < i; j++) {
DP[u][i] = max(DP[u][i], DP[v][j] + DP[u][i - j]);
}
}
}
}
signed main() {
IOS;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int f;
cin >> f >> DP[i][1];
G[f].push_back(i);
}
dfs(0);
cout << DP[0][m + 1] << endl;
return 0;
}
H. k步以内
- DP1表示子树的， DP2表示不是子树的，每个长度的都要记录
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
64define MAX 100005
int DP1[MAX][30], DP2[MAX][30];
int n, m;
int val[MAX];
vector<int> G[MAX];
void dfs1(int u, int fa)
{
for (int i = 0; i <= m; i++)
{
DP1[u][i] = val[u];
}
for (int v : G[u])
{
if (v == fa)
continue;
dfs1(v, u);
for (int i = 1; i <= m; i++)
{
DP1[u][i] += DP1[v][i - 1];
}
}
}
void dfs2(int u, int fa)
{
if (u != 1)
{
DP2[u][0] = 0;
DP2[u][1] = val[fa];
for (int i = 2; i <= m; i++)
{
DP2[u][i] = DP1[fa][i - 1] - DP1[u][i - 2] + DP2[fa][i - 1];
}
}
for (int v : G[u])
{
if (v == fa)
continue;
dfs2(v, u);
}
}
signed main()
{
IOS;
cin >> n >> m;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
G[u].push_back(v), G[v].push_back(u);
}
for (int i = 1; i <= n; i++)
{
cin >> val[i];
}
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; i++)
{
cout << DP1[i][m] + DP2[i][m] << endl;
}
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ysmmm的快乐小屋！
