整理的算法模板合集： ACM模板
实际上是一个全新的精炼模板整合计划
BZOJ简单题合集x
目录
BZOJ 1592. Making the Grade
Weblink
https://hydro.ac/d/bzoj/p/1592
Problem
Solution
题目要求通过修改得到非严格单调递增或递减的序列，也就是说可以相等。所以这里有一个非常显然的结论：最少的修改次数得到非严格单调的序列，修改后的得到的数一定是原序列里的数。（因为可以相等，贪心的想一想，为什么）
那么显然我们可以设 f [ i , j ] f[i,j] f[i,j] 表示序列中第 i i i 个数修改为原序列里第 j j j 个数的最少修改次数。
题目中序列可以为非严格单调递增或者非严格单调递减，所以我们将原序列复制为 b b b 数组，将 b b b 递增排序进行DP，然后递减排序进行DP取二者最小值即可。
显然有转移方程：
f [ i , j ] = min { f [ i − 1 , k ] + abs ( a [ i ] − b [ j ] ) , 1 ≤ k ≤ j } f[i,j]=\min\{f[i-1,k]+\text{abs}(a[i]-b[j]),1\le k\le j\} f[i,j]=min{f[i−1,k]+abs(a[i]−b[j]),1≤k≤j}
直接转移时间复杂度为 O ( n 3 ) O(n^3) O(n3)， n ≤ 2000 n\le 2000 n≤2000，考虑优化。
考虑经典优化：数据结构优化。
显然有：
f [ i , j ] = min { f [ i − 1 , k ] + abs ( a [ i ] − b [ j ] ) , 1 ≤ k ≤ j } f [ i , j ] = min { min { f [ i − 1 , k ] , 1 ≤ k ≤ j } + abs ( a [ i ] − b [ j ] ) } f[i,j]=\min\{f[i-1,k]+\text{abs}(a[i]-b[j]),1\le k\le j\}\\ f[i,j]=\min\{\min\{f[i-1,k],1\le k\le j\}+\text{abs}(a[i]-b[j])\} f[i,j]=min{f[i−1,k]+abs(a[i]−b[j]),1≤k≤j}f[i,j]=min{min{f[i−1,k],1≤k≤j}+abs(a[i]−b[j])}
即决策集合中的元素只增不减，我们就可以用一个数据结构来维护这个决策集合，也即维护 min { f [ i − 1 , k ] , 1 ≤ k ≤ j } \min\{f[i-1,k],1\le k\le j\} min{f[i−1,k],1≤k≤j} 即可。
这里显然使用一个变量维护即可。
我们维护 num = min { f [ i − 1 , k ] , 1 ≤ k ≤ j } \text{num}=\min\{f[i-1,k],1\le k\le j\} num=min{f[i−1,k],1≤k≤j}，每次转移的时候直接取 num = min { f [ i , j ] , f [ i − 1 , j ] } \text{num}=\min\{f[i,j],f[i-1,j]\} num=min{f[i,j],f[i−1,j]}，在DP转移的时候 f [ i , j ] f[i,j] f[i,j] 直接用 num \text{num} num 进行更新即可。
Code
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int maxn = 2e3 + 6, maxm = 1e6 + 7, INF = 0x3f3f3f3f;
int n, m, s, t;
int a[maxn], b[maxn];
ll f[maxn][maxn];
ll ans;
int main()
{
ans = INF;
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
b[i] = a[i];
}
memset(f, 0x3f, sizeof f);
sort(b + 1, b + 1 + n);
for (int j = 1; j <= n; ++ j)
f[0][j] = 0;
for (int i = 1; i <= n; ++ i) {
ll num = INF;
for (int j = 1; j <= n; ++ j) {
num = min(num, f[i - 1][j]);
f[i][j] = min(f[i][j], num + abs(a[i] - b[j]));
}
}
for (int j = 1; j <= n; ++ j)
ans = min(ans, f[n][j]);
memset(f, 0x3f, sizeof f);
reverse(b + 1, b + 1 + n);
for (int i = 1; i <= n; ++ i) {
ll num = INF;
for (int j = 1; j <= n; ++ j) {
num = min(num, f[i - 1][j]);
f[i][j] = min(f[i][j], num + abs(a[i] - b[j]));
}
}
for (int j = 1; j <= n; ++ j)
ans = min(ans, f[n][j]);
cout << ans << endl;
return 0;
}
拓展问题一
拓展问题一：给定长度为 n n n 的整数序列 a a a ，求最少修改次数（修改操作可以任意修改数值），使得 a a a 非严格单调递增。（保证序列任意时刻均为整数）
Solution
显然问题的答案为 n − L I S n-LIS n−LIS，即贪心地使得不需要修改的数尽可能的多。
拓展问题二
拓展问题二：给定长度为 n n n 的整数序列 a a a ，求最少修改次数（修改操作可以任意修改数值），使得 a a a 严格单调递增。（保证序列任意时刻均为整数）
Solution
同样考虑贪心策略，使得不需要修改的数尽可能的多。
显然对于任意的
j
>
i
j>i
j>i ，
i
i
i 和
j
j
j 可以保留当且仅当
a
[
j
]
>
a
[
i
]
a
n
d
a
[
j
]
−
a
[
i
]
≥
j
−
i
a[j]>a[i]\ \mathrm{and}\ a[j]-a[i]\ge j-i
a[j]>a[i] and a[j]−a[i]≥j−i
也即
a [ j ] − j ≥ a [ i ] − i a[j]-j \ge a[i]-i a[j]−j≥a[i]−i
因此我们让 a[i] = a[i] - i，问题就转化为了问题一，答案为
n
−
L
I
S
n-LIS
n−LIS。
O ( n log n ) O(n\log n) O(nlogn) 求解新序列的 L I S LIS LIS 即可。
拓展问题三
Weblink
Problem
给你一个数列 a a a，一个 k k k 个元素的集合 b b b ，对于每个 b b b 中的元素 x x x， a x a_x ax 不能修改，其他都可以修改，问最少多少次可以将 a a a 修改为严格单调递增的。如果不存在，输出 − 1 -1 −1。
a a a 中的所有元素在任意时刻必须都是整数
1 ≤ n ≤ 5 × 1 0 5 , 1 ≤ a i ≤ 1 0 9 1\le n\le5\times 10^5,1 \le a_i \le 10^9 1≤n≤5×105,1≤ai≤109。
Solution
本题增加了一个新限制条件，即有 k k k 个点不能修改。
显然是没有什么用的，我们将序列分为 k + 1 k+1 k+1 段，分别对每段计算答案即可（段内有序，段间有序）。
二分 O ( n log n ) O(n\log n) O(nlogn) 计算 L I S LIS LIS 即可。
Code
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int maxn = 5e5 + 6, maxm = 1e6 + 7, INF = 0x3f3f3f3f;
int n, m, s, t;
int a[maxn], b[maxn];
ll f[maxn];
ll ans;
vector<int> LIS;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i) {
int x;
scanf("%d", &x);
a[i] = x - i;
}
a[0] = -INF;
a[n + 1] = INF;
for (int i = 1; i <= m; ++ i)
scanf("%d", &b[i]);
b[0] = 0;
b[m + 1] = n + 1;
for (int i = 0; i <= m; ++ i) {
int l = b[i], r = b[i + 1];
if (a[l] > a[r])
return 0 * puts("-1");
LIS.clear();
for (int j = l + 1; j <= r - 1; ++ j) {
if (a[j] >= a[l] && a[j] <= a[r]) {
auto pos = upper_bound(LIS.begin(), LIS.end(), a[j]);
if (pos == LIS.end())
LIS.push_back(a[j]);
else *pos = a[j];
}
}
ans += (r - l - 1) - LIS.size();
}
cout << ans << endl;
return 0;
}