- 纸杯正反放置问题
- 该题的题意是，给定一个长度为3≤n≤2000 的01串（令下标为1 ~ n），要求对若干个位置进行反转（0变1，1变0），使得最终的串变为前段全为1，中间全为0，后段全为1，且每段的长度不得小于1，即最终的串能找到一对x和y满足 1<x<y<n 且 1~x 的位置全为1；x+1~y 的位置全为0； y+1~n 的位置全为1。求出最小反转次数 。
- 把串分成101三段，可以想象成找两个分割点，将串切成三段。第1、3段要求全1，那么反转次数就是其中0的个数；同理第二段反转的次数就是其中1的个数。我们可以枚举两个分割点，然后分别统计三段反转的次数求和，最终找到最小值就是我们要的答案了。
- 统计某一段的反转次数，上面说了，其实就是其中0或者1的数量。这个东西我们可以预处理一个前缀和来快速得到，两个前缀和作差我们就可以得到这个区间里1的个数，区间长度减去1的个数那就是0的个数。
- 这个做法枚举分割点的时间复杂度是O(n2)，预处理前缀和的时间复杂度是O(n)，统计区间内0、1的数量时间复杂度是O(1)，总的复杂度是O(n2)
// n为串长，a为初始的01串，下标范围在1~n
int solve(int n, int a[]) {
int pre[n + 1] = {0};
// 计算前缀和
for (int i = 1; i <= n; ++i) {
pre[i] = pre[i - 1] + a[i];
}
/*
这里枚举i,j作为分割点
令i是第二段的起始位置，j是第三段的起始位置
由于每段的长度都不得少于1，所以要注意i,j的枚举范围
*/
int ans = n + 114514; // 这里先给答案初始化一个足够大的值
for (int i = 2; i < n; ++i) for (int j = i + 1; j <= n; ++j) {
int sum = 0;
sum += (i - 1) - pre[i - 1]; // 第一段 1~i-1 中 0 的数量
sum += pre[j - 1] - pre[i - 1]; // 第二段 i~j-1 中 1 的数量
sum += (n - j + 1) - (pre[n] - pre[j - 1]); // 第三段 j~n 中 0 的数量
ans = std::min(ans, sum);
}
return ans;
}
- 假设我们现在通过某种方式得到了一个数组 preAns[]，preAns[k] 表示串的前k个位置作为第1、2段的最小反转次数，那显然我们就只需要用一重循环来枚举第2、3段的分割点y，然后统计 preAns[y-1]+(y~n 中0的个数) 的最小值即为最终的答案。
- 此时问题变成了如何快速求出数组 preAns[]。同样的我们先考虑下用暴力枚举的方法如何求出 preAns[]
for (int i = 1; i <= n; ++i) {
int res = n + 114514; // 这里初始化一个足够大的值
// 枚举j是第1、2段的分割点
for (int j = 2; j <= i; ++j) {
int sum = 0;
sum += (j - 1) - pre[j - 1]; // 第一段 1~j-1 中 0 的数量
sum += pre[i] - pre[j - 1]; // 第二段 j~i 中 1 的数量
res = std::min(res, sum);
}
preAns[i] = res;
}
- 这时候你可能会说，“诶，这样搞不是不还是n方吗”，是的没错，假如我们还是暴力去求 preAns[]，那么最终的时间复杂度就还是O(n2)
- 我们整理一下上面求 preAns[] 的式子，preAns[i] = min_{i=1}^n\{(j-1)-pre[j-1]+pre[i]-pre[j-1]\} = min_{i=1}^n\
- 整理后可以发现减号后面的式子是一个关于 j-1 的式子。我们引入一个临时变量，令 tmp[k] = 2*pre[k]-k，那么原式就变成了preAns[i]=mini=1n{pre[i]−tmp[j−1])}，为了使大括号内的值尽量小，也就是要找到一个2≤j≤i，使得 tmp[j - 1] 尽量大。
for (int i = 1; i <= n; ++i) {
int res = 0;
// 枚举j是第1、2段的分割点
for (int j = 2; j <= i; ++j) {
res = std::max(res, 2 * pre[j - 1] - (j - 1));
}
preAns[i] = pre[i] - res;
}
- 注意到 j-1 是比 i 要小的，我们可以在枚举 i 的过程中同时维护 tmp[j-1] 的最大值，这样就可以把枚举 j 的循环优化掉，这样我们就可以在O(n)的时间复杂度内求出 preAns[]
- 这个做法枚举预处理前缀和的时间复杂度是O(n)，统计区间内0、1的数量时间复杂度是O(1)，预处理 preAns[] 的时间复杂度是O(n)，最终枚举第2、3段分割点的时间复杂度也是O(n)，总的复杂度是O(n)
// n为串长，a为初始的01串，下标范围在1~n
int solve(int n, int a[]) {
static const int INF = n + 114514;
int pre[n + 1] = {0};
// 计算前缀和
for (int i = 1; i <= n; ++i) {
pre[i] = pre[i - 1] + a[i];
}
int preAns[n + 1];
int maxTmp = -INF; // 维护tmp[j-1]的最大值，初始化一个足够小的值
for (int i = 1; i <= n; ++i) {
preAns[i] = pre[i] - maxTmp;
maxTmp = std::max(maxTmp, 2 * pre[i] - i); // 注意！由于j-1是严格小于i的，这里要先更新preAns[]，再更新maxTmp。
}
// 这里枚举第2、3段的分割点
int ans = INF; // 这里初始化一个足够大的值
for (int i = 3; i <= n; ++i) {
int sum = preAns[i - 1] + (n - i + 1) - (pre[n] - pre[i - 1]); // 1~i-1 分成1、2段的最少反转次数，加上 i~n 中 0 的数量
ans = std::min(ans, sum);
}
return ans;
}
- 简单来说就是每个位置都有3种状态，分别表示当前位置处于第1、2、3段。在状态转移的时候考虑当前位置是接上前一个位置作为一段，还是自己作为新一段的开头。废话不多说直接上ppt
