集训 DP 专场 01 (9/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
|
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 50;
long long f[N];
void init() {
f[1] = 1, f[2] = 1, f[3] = 2;
for (int i = 4; i < N; i++) {
f[i] = f[i - 1] + f[i - 2];
}
}
int main() {
init();
int n; cin >> n;
while (n--) {
int x; scanf("%d", &x);
printf("%lld\n", f[x]);
}
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
|
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int w[N][N];
int f[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++)
cin >> w[i][j];
}
for (int i = n; i; i--) {
for (int j = i; j; j--)
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + w[i][j];
}
cout << f[1][1] << endl;
return 0;
}
|
做法：求两段不相交区间和的最大值。正反dp一遍求出 $i$ 和 $i$ 左侧的连续区间的最大和，$i$ 和 $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
|
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 50010;
int n, T;
LL a[N];
LL f[N], g[N];
void solve() {
scanf("%d", &n);
memset(f, -0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++) f[i] = max(a[i], f[i - 1] + a[i]);
for (int i = n; i >= 1; i--) g[i] = max(a[i], g[i + 1] + a[i]);
for (int i = 1; i <= n; i++) f[i] = max(f[i], f[i - 1]);
for (int i = n; i >= 1; i--) g[i] = max(g[i], g[i + 1]);
LL res = -1e18;
for (int i = 1; i <= n - 1; i++) res = max(res, f[i] + g[i + 1]);
cout << res << endl;
}
int main() {
cin >> T;
while (T--) solve();
return 0;
}
|
做法：最后的序列一定是 0000111 形式的，求非严格 LIS 即可。
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
|
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N], f[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++) {
if (a[j] <= a[i])
f[i] = max(f[i], f[j] + 1);
}
}
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, f[i]);
cout << res << endl;
return 0;
}
|
去年做过的一个题：https://ketchuppp.xyz/post/Codeforces10D-LCIS/
开始还想怎么区间dp，一看数据范围就不太行。
做法：贪心、思维题。最优的情况一定是，只有相邻两项取了差值的绝对值，其他项都可以取到自身的绝对值。所以只要暴力循环一遍，$i$ 和 $i+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
|
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 500010;
int n;
LL a[N], b[N];
int main() {
cin >> n;
LL sum = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
b[i] = abs(a[i]);
sum += b[i];
}
LL res = 0;
for (int i = 1; i <= n - 1; i++) {
// i, i+1
res = max(res, sum - (b[i] + b[i + 1]) + abs(a[i] - a[i + 1]));
}
if (n == 1) cout << a[1] << endl;
else cout << res << endl;
return 0;
}
|
$f[i]$ 表示将前 $i$ 个分割成回文串的最小个数，暴力枚举一下 $j$，$[j,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
|
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1010;
int n, T;
int f[N]; // f[i]表示将前i个分割成回文串的最小个数
char s[N];
bool check(int l, int r) {
int i = l, j = r;
bool flag = true;
while (i < j) {
if (s[i] != s[j]) {
flag = false;
break;
}
i++, j--;
}
return flag;
}
void solve() {
scanf("%s", s + 1);
n = strlen(s + 1);
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; i++) {
f[i] = f[i - 1] + 1;
for (int j = 1; j < i; j++) {
if (check(j, i)) {
f[i] = min(f[i], f[j - 1] + 1);
}
}
}
// cout << check(3, 5) << endl;
// cout << f[5] << endl;
cout << f[n] << endl;
}
int main() {
cin >> T;
while (T--) solve();
return 0;
}
|
题意：给定 $n$ 个数，分成 $k$ 组，要求组内最大值和最小值的差值不超过 $5$，问 $k$ 组最多能包含几个数。
做法：$f[i][j]$ 表示前 $i$ 个人中分了 $j$ 组的最大人数。以第 $i$ 个人在不组内来划分。 $i$ 不在组内 $f[i][j]=f[i-1][j]$，$i$ 组内 $f[i][j]=f[t-1][j-1]+i-t+1$，其中 $t$ 是第 $j-1$ 组中的最小值的下标，二分查找 $t$。
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 <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5010;
int n, k;
int a[N];
int f[N][N];
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k && j <= i; j++) {
f[i][j] = f[i - 1][j]; // 不选
int t = lower_bound(a + 1, a + i + 1, a[i] - 5) - a;
f[i][j] = max(f[i][j], f[t - 1][j - 1] + i - t + 1);
res = max(res, f[i][j]);
}
}
cout << res << endl;
return 0;
}
|
题意：每次可以分割字符串，然后把前面一部分接到后面取，给定步数，原串，目标串，问原串经过特定步数能通过多少种方式变成目标串。
妙啊（然而根本想不到
做法：$f[i][0]$ 表示走了 $i$ 步现在为目标串的所有方案数，$f[i][1]$ 表示走了 $i$ 步现在为非目标串的所有方案数。则答案为 $f[k][0]$。
先把原串看成一个环，从任意位置切开，记录能变成目标串的切割数 $cnt$。
如果第 $i$ 步已经成为了目标串，可以从 $f[i-1][0]$ 和 $f[i-1][1]$ 转移。若 $i-1$ 步已经是目标串了，那么第 $i$ 仍然是目标串，只能从 $cnt-1$ 个位置切；若 $i-1$ 步为非目标串，那么就有 $cnt$ 种切法转化为目标串。
如果第 $i$ 为非目标串，可以从 $f[i-1][0]$ 和 $f[i-1][1]$ 转移。若 $i-1$ 步是目标串了，现在要变成非目标串，只能从 $n-cnt$ 个位置切；若 $i-1$ 步为非目标串，现在要保持非目标串，那么就有 $n-1-cnt$ 种切法（首先不能选择 $cnt$ 个会变成目标串的切法，又不能切成自己当前的状态不然就相当于没切）。
数据范围较小，否则需要 KMP 来做第一步的匹配；另外可以用滚动数组优化一下空间。
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 <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 2010, mod = 1e9 + 7;
int n, k;
char a[N], b[N];
LL f[2][2]; // f[i][0]表示第i步变成了b串的方案数,f[i][1]表示第i步变成了非b串的方案数
bool check(int start) {
bool flag = true;
for (int i = start, j = 0; i <= start + n - 1; i++, j++) {
if (a[i] != b[j]) {
flag = false;
break;
}
}
return flag;
}
int main() {
int cnt = 0;
scanf("%s%s%d", a, b, &k);
n = strlen(a);
for (int i = 0; i < n; i++) {
a[n + i] = a[i];
if (check(i)) cnt++;
}
f[0][!check(0)] = 1; // check为true表示a=b
for (int i = 1; i <= k; i++) {
f[i & 1][0] = (f[i - 1 & 1][0] * (cnt - 1) + f[i - 1 & 1][1] * cnt) % mod;
f[i & 1][1] = (f[i - 1 & 1][0] * (n - cnt) + f[i - 1 & 1][1] * (n - 1 - cnt)) % mod;
}
cout << f[k & 1][0] << endl;
return 0;
}
|