题 0X00
题目传送门
CF1324E Sleeping Schedule
分析
这个题由于每次都需要选择，是在ai-1时睡还是ai时睡，那么很明显，这个题需要用动态规划来写。
对于所有的动态规划问题，我们首先都是找他们的关系式。
对于这个题而言，对答案的影响是在于小明在[l,r]这段时间内入睡的次数，那么，我们就设一个数组 $ dp[i][j] $ ，表示小明的第i次睡眠在第j小时开始入睡能够获得的最大的 $ ans $ 。那么，由于小明睡觉的时间有两种情况，因此，我们就可以直接进行分类讨论：
如果小明选择过 $ a_i $ 这么多时间睡觉，那么：
如果 $ (j + a[i]) % h >= l $ 并且 $ (j + a[i]) % h <= r $ ,那么有 $ dp[i][(j + a[i]) % h]=max{dp[i - 1][j] + 1} $
否则，则有 $ dp[i][(j + a[i]) % h] = max{dp[i - 1][j]} $
如果小明选择过 $ a_i-1 $ 这么多时间睡觉，那么：
如果 $ (j + a[i] - 1) % h >= l $ 并且 $ (j + a[i] - 1) % h <= r $ ,那么有 $ dp[i][(j + a[i] - 1) % h]=max{dp[i - 1][j] + 1} $
否则，则有 $ dp[i][(j + a[i] - 1) % h] = max{dp[i - 1][j]} $
最后的答案就是 $ dp[n][i] $ 中最大的那个。
AC代码
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 <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2005;
int n, h, l, r, a[MAXN], sum = 0, f[MAXN][MAXN];
int main() {
scanf("%d%d%d%d", &n, &h, &l, &r);
memset(f, -0x3f3f3f3f, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= n; i ++) {
for(int j = 0; j < h; j ++) {
if((j + a[i]) % h >=l && (j + a[i]) % h <= r) {
f[i][(j + a[i]) % h] = max(f[i][(j + a[i]) % h], f[i - 1][j] + 1);
}
else {
f[i][(j + a[i]) % h] = max(f[i][(j + a[i]) % h], f[i-1][j]);
}
if((j + a[i] - 1) % h >= l && (j + a[i] - 1) % h <= r) {
f[i][(j + a[i] - 1) % h] = max(f[i][(j + a[i] - 1) % h], f[i - 1][j] + 1);
}
else {
f[i][(j + a[i] - 1) % h] = max(f[i][(j + a[i] - 1) % h], f[i - 1][j]);
}
}
}
for(int i = 0; i <= h; i ++) {
if(f[n][i] > sum) {
sum = f[n][i];
}
}
printf("%d", sum);
return 0;
}
|
有图证AC
题 0X01
题目传送门
Codeforces 628B
分析
由于我们知道，$ 100 $ 是 $ 4 $ 的倍数，那么，对于一个大于 $ 100 $ 的数字，只需要判断这个数字的最小的两位组成的数字能否被 $ 4 $ 整除即可。因此，我们只需要
- 首先判断第一个数是不是 $ 4 $ 的倍数，如果是就加 $ 1 $ 。
- 从第二位开始，如果第 $ i $ 位数能被 $ 4 $ 整除，答案 $ +1 $ ，如果以 $ i $ 和 $ i-1 $ 位的两个数字组成的两位数是 $ 4 $ 的倍数，那么答案就 $ +i $ （比如 $ 124 $ ，首先是 $ 1 $ ，不是 $ 4 $ 的倍数，就不管，然后是 $ 12 $ , $ 2 $ 不是 $ 4 $ 的倍数，但是 $ 12 $ 是，所以答案就加上 $ i=1 $ ，然后是 $ 124 $ ，因为 $ 4 $ 是 $ 4 $ 的倍数，所以答案 $ +1=2 $ ，然后 $ 24 $ 也是 $ 4 $ 的倍数，所以答案 $ +2=4 $ ）。
AC代码
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 3 * 1e5 + 5;
char str[MAXN];
long long sum = 0, len, a[MAXN];
int main() {
scanf("%s", str);
len = strlen(str);
for(int i = len; i >= 1; i --) {
a[i] = str[len - i] - '0';
}
for(int i = 1; i <= len; i ++) {
if(a[i] % 4 == 0) {
sum ++;
}
if(i < len && (a[i] + a[i + 1] * 10) % 4 == 0) {
sum += len - i;
}
}
printf("%lld", sum);
return 0;
}
|
题 0X02
题目传送门
Codeforces 1207C
分析
一看到这种有选择的题，就知道要么是搜索，要么是DP。由于这个题每个状态都只和相邻的状态有关，因此，这个题也是用DP来做。
我们设 $ dp[i][j] $ 表示第 $ i $ 个路口右边的支柱为 $ j $ 这么高的所需要的最小花费。
如果这个路口是 $ 1 $ ，那么，此时右边和左边的支柱就只能是高度为 $ 2 $ 的支柱。
于是就有：
1
| dp[i][1]=max{dp[i-1][1]+a+2b}
|
如果这个路口是 $ 0 $ ，那么，右边的支柱可以是高支柱，也可以是矮支柱。
如果右边的支柱是矮支柱，那么：
1
| dp[i][0]=max{min(dp[i-1][0]+a+b,dp[i-1][1]+2a+b)}
|
如果是高支柱，那么：
1
| dp[i][1]=max{min(dp[i-1][0]+2a+2b,dp[i-1][1]+a+2b)}
|
由于最后一个路口一定是 $ 0 $ ，所以最后答案直接输出 $ dp[n][0] $ 。
另外考虑到有些不会出现的情况，为了不影响我们的答案，所以所有的数据初始化为 $ INF $ 。
AC代码
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2 * 1e5 + 5;
long long t, n, a, b, f[MAXN][5];
char dl[MAXN];
int main() {
scanf("%lld", &t);
while(t --) {
scanf("%lld%lld%lld\n", &n, &a, &b);
for(int i = 1; i <= n; i ++) {
scanf("%c", &dl[i]);
}
memset(f, 0x3f3f3f3f, sizeof(f));
f[0][0] = b;
for(int i = 1; i <= n; i ++) {
if(dl[i] == '1') {
f[i][1] = min(f[i][1], f[i - 1][1] + a + 2 * b);
}
else {
f[i][0] = min(f[i][0], min(f[i - 1][0] + a + b, f[i - 1][1] + 2 * a + b));
f[i][1] = min(f[i][1], min(f[i - 1][0] + 2 * a + 2 * b, f[i - 1][1] + a + b * 2));
}
}
printf("%lld\n", f[n][0]);
}
return 0;
}
|
题 0X01
题目传送门
Codeforces 628B
分析
由于我们知道，$ 100 $ 是 $ 4 $ 的倍数，那么，对于一个大于 $ 100 $ 的数字，只需要判断这个数字的最小的两位组成的数字能否被 $ 4 $ 整除即可。因此，我们只需要
- 首先判断第一个数是不是 $ 4 $ 的倍数，如果是就加 $ 1 $ 。
- 从第二位开始，如果第 $ i $ 位数能被 $ 4 $ 整除，答案 $ +1 $ ，如果以 $ i $ 和 $ i-1 $ 位的两个数字组成的两位数是 $ 4 $ 的倍数，那么答案就 $ +i $ （比如 $ 124 $ ，首先是 $ 1 $ ，不是 $ 4 $ 的倍数，就不管，然后是 $ 12 $ , $ 2 $ 不是 $ 4 $ 的倍数，但是 $ 12 $ 是，所以答案就加上 $ i=1 $ ，然后是 $ 124 $ ，因为 $ 4 $ 是 $ 4 $ 的倍数，所以答案 $ +1=2 $ ，然后 $ 24 $ 也是 $ 4 $ 的倍数，所以答案 $ +2=4 $ ）。
AC代码
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 3 * 1e5 + 5;
char str[MAXN];
long long sum = 0, len, a[MAXN];
int main() {
scanf("%s", str);
len = strlen(str);
for(int i = len; i >= 1; i --) {
a[i] = str[len - i] - '0';
}
for(int i = 1; i <= len; i ++) {
if(a[i] % 4 == 0) {
sum ++;
}
if(i < len && (a[i] + a[i + 1] * 10) % 4 == 0) {
sum += len - i;
}
}
printf("%lld", sum);
return 0;
}
|
题 0X02
题目传送门
Codeforces 1207C
分析
一看到这种有选择的题，就知道要么是搜索，要么是DP。由于这个题每个状态都只和相邻的状态有关，因此，这个题也是用DP来做。
我们设 $ dp[i][j] $ 表示第 $ i $ 个路口右边的支柱为 $ j $ 这么高的所需要的最小花费。
如果这个路口是 $ 1 $ ，那么，此时右边和左边的支柱就只能是高度为 $ 2 $ 的支柱。
于是就有：
1
| dp[i][1]=max{dp[i-1][1]+a+2b}
|
如果这个路口是 $ 0 $ ，那么，右边的支柱可以是高支柱，也可以是矮支柱。
如果右边的支柱是矮支柱，那么：
1
| dp[i][0]=max{min(dp[i-1][0]+a+b,dp[i-1][1]+2a+b)}
|
如果是高支柱，那么：
1
| dp[i][1]=max{min(dp[i-1][0]+2a+2b,dp[i-1][1]+a+2b)}
|
由于最后一个路口一定是 $ 0 $ ，所以最后答案直接输出 $ dp[n][0] $ 。
另外考虑到有些不会出现的情况，为了不影响我们的答案，所以所有的数据初始化为 $ INF $ 。
AC代码
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2 * 1e5 + 5;
long long t, n, a, b, f[MAXN][5];
char dl[MAXN];
int main() {
scanf("%lld", &t);
while(t --) {
scanf("%lld%lld%lld\n", &n, &a, &b);
for(int i = 1; i <= n; i ++) {
scanf("%c", &dl[i]);
}
memset(f, 0x3f3f3f3f, sizeof(f));
f[0][0] = b;
for(int i = 1; i <= n; i ++) {
if(dl[i] == '1') {
f[i][1] = min(f[i][1], f[i - 1][1] + a + 2 * b);
}
else {
f[i][0] = min(f[i][0], min(f[i - 1][0] + a + b, f[i - 1][1] + 2 * a + b));
f[i][1] = min(f[i][1], min(f[i - 1][0] + 2 * a + 2 * b, f[i - 1][1] + a + b * 2));
}
}
printf("%lld\n", f[n][0]);
}
return 0;
}
|