本文最后更新于：2022年10月27日 晚上
问题
基础的二分答案掌握尚不牢固（太丢人了）。
实际问题考虑不周全（更丢人了，甚至不和 0 取 $\max$）。
码力还是不够强，斗地主没两个月就写不出来了（更进一步的丢人了）。
DP 还是弄不出来，还是得练。
Solution
P2678
这居然还不能全对着实丢大人了。
具体错误：
上来没有快速排序，石头的位置并不是有序的！
check 函数中判断石头挪走后，没有正确处理该和哪一个石头对比距离，应当是沿用之前的石头而不是上一个石头。
为什么上来要拿走当前的石头呢？因为拿走靠后一点的会给后面的留下更多选择的余地，这样比拿走上一个肯定更好一点，至少不会亏本。
1
2
3
4
5
6
7
8
9
10
11
| bool check(ll x) {
int now = 0, pos = 0, tot = 0;
while(now < n + 1) {
++now;
if(a[now] - a[pos] < x) ++tot;
else pos = now;
}
return tot <= m;
}
|
P2668
总而言之还是多写几遍吧，码力还是不够强。
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| void dfs(int x) {
if(x >= ans) return ;
int len = 0;
for(int i = 3; i <= 14; ++i) {
if(a[i] == 0) len = 0;
else {
++len;
if(len >= 5) {
for(int j = i; j >= i - len + 1; --j) --a[j];
dfs(x + 1);
for(int j = i; j >= i - len + 1; --j) ++a[j];
}
}
}
len = 0;
for(int i = 3; i <= 14; ++i) {
if(a[i] < 2) len = 0;
else {
++len;
if(len >= 3) {
for(int j = i; j >= i - len + 1; --j) a[j] -= 2;
dfs(x + 1);
for(int j = i; j >= i - len + 1; --j) a[j] += 2;
}
}
}
len = 0;
for(int i = 3; i <= 14; ++i) {
if(a[i] < 3) len = 0;
else {
++len;
if(len >= 2) {
for(int j = i; j >= i - len + 1; --j) a[j] -= 3;
dfs(x + 1);
for(int j = i; j >= i - len + 1; --j) a[j] += 3;
}
}
}
for(int i = 2; i <= 14; ++i) {
if(a[i] <= 3) {
if(a[i] <= 2) continue;
a[i] -= 3;
for(int j = 2; j <= 15; ++j) {
if(a[j] <= 0 || j == i) continue;
--a[j];
dfs(x + 1);
++a[j];
}
for(int j = 2; j <= 14; ++j) {
if(a[j] < 2 || j == i) continue;
a[j] -= 2;
dfs(x + 1);
a[j] += 2;
}
a[i] += 3;
} else {
a[i] -= 3;
for(int j = 2; j <= 15; ++j) {
if(a[j] < 1 || j == i) continue;
--a[j];
dfs(x + 1);
++a[j];
}
for(int j = 2; j <= 14; ++j) {
if(a[j] < 2 || j == i) continue;
a[j] -= 2;
dfs(x + 1);
a[j] += 2;
}
a[i] += 3;
a[i] -= 4;
for(int j = 2; j <= 15; ++j) {
if(a[j] <= 0 || j == i) continue;
--a[j];
for(int k = 2; k <= 15; ++k) {
if(a[k] <= 0 || j == k) continue;
--a[k];
dfs(x + 1);
++a[k];
}
++a[j];
}
for(int j = 2; j <= 14; ++j) {
if(a[j] < 2 || j == i) continue;
a[j] -= 2;
for(int k = 2; k <= 14; ++k) {
if(a[k] < 2 || k == j) continue;
a[k] -= 2;
dfs(x + 1);
a[k] += 2;
}
a[j] += 2;
}
a[i] += 4;
}
}
for(int i = 2; i <= 15; ++i)
if(a[i]) ++x;
ans = min(ans, x);
}
|