序列变换 HDU - 5256 (LIS + 数学思维)
做这道题的基础就是二分+贪心版本的LIS, 还不是很懂的同学请参考https://blog.****.net/a1097304791/article/details/82286906
再来说这个题, 很显然就像是LIS的题目, 但是情况稍有不同
举个栗子来说, 对于1 2 3 4 4 4 5 来说, 最长LIS是4(12345), 但需要修改3个元素, 问题就出在这里, 题面要求只能修改元素大小, 不能删除, 而且必须严格递增, 也就是说相邻元素不能相等.
用数学表述即: a[i+1] >= a[i]+1 (1)
可推的: a[i]-(i+1) >= a[i]-i (2)
说明想要满足(1), 只需满足(2)即可, 所以我们预处理所有的a[i] = a[i] - i, 然后求此序列的LIS = len, n-len即为答案
总结: 对数学预处理思想的掌握
//序列变换
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL;
const LL maxn = 1e5+10;
int T, n, a[maxn], b[maxn];
int bSearch(int tar, int l, int r)
{
//返回b中第一个大于tar的数下标
while(l <= r){
int mid = (l+r)/2;
if(tar >= b[mid]) l = mid+1;
else r = mid-1;
}
return l;
}
int solve()
{
int len = 1;
b[1] = a[1];
for(int i = 2; i <= n; i++){
if(a[i] >= b[len]) b[++len] = a[i]; //直接加到最后
else if(a[i] < b[len])
b[bSearch(a[i], 1, len)] = a[i]; //ai替换b中第一个比ai大的数
}
return n-len;
}
int main()
{
cin >> T;
for(int t = 1; t <= T; t++){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
a[i] -= i; //预处理a (a[i] = a[i]-i)
}
printf("Case #%d:\n%d\n", t, solve());
ms(a, 0); ms(b, 0);
}
return 0;
}