BZOJ 1592. Making the Grade(思维,数据结构优化DP,以及三个拓展问题)[Usaco2008 Feb]【BZOJ计划】

整理的算法模板合集: ACM模板

点我看算法全家桶系列!!!

实际上是一个全新的精炼模板整合计划


BZOJ简单题合集x

目录

BZOJ 1592. Making the Grade

Weblink

https://hydro.ac/d/bzoj/p/1592

Problem

BZOJ 1592. Making the Grade(思维,数据结构优化DP,以及三个拓展问题)[Usaco2008 Feb]【BZOJ计划】
BZOJ 1592. Making the Grade(思维,数据结构优化DP,以及三个拓展问题)[Usaco2008 Feb]【BZOJ计划】

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

CF1437E Make It Increasing

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;
}
上一篇:回退merge后未做操作的代码


下一篇:【Pandas】根据某列分组求和