hdu 5256 序列变换-LIS 严格转非严格

http://acm.hdu.edu.cn/showproblem.php?pid=5256 我们有一个数列A1,A2...An，你现在要求修改数量最少的元素，使得这个数列严格递增。其中无论是修改前还是修改后，每个元素都必须是整数。 请输出最少需要修改多少个元素。

 

N<=1e5

如果是严格递增的话，是不太好处理的，如果换成非严格递增的话，我们只需要求一遍非严格的lis,然后n-maxlen就是答案了

如果把一个求严格递增的序列转换为非严格递增的序列呢？

推导过程大致如下：a[i] < a[i+1] ——> a[i] <= a[i+1]-1 ——> a[i]-i <= a[i+1]-(i+1)——> b[i]<=b[i+1]

也就是令b[i]=a[i]-i就可以了。

城市套路多 #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <set> #include <vector> #include <iostream> using namespace std; const int maxn = 100010; int arr[maxn],ans[maxn]; int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int t; int cnt=1; cin>>t; while(t--) { int n,idx=0; scanf("%d",&n); for (int i=1; i<=n; i++) { int x; scanf("%d",&x); arr[++idx]=x-i; } n=idx; //memset(ans,0,sizeof(ans)); ans[1] = arr[1]; int len=0; if (n>=1) len=1; for(int i=2; i<=n; ++i) { if(arr[i]>=ans[len]) //*****fei严格 ans[++len]=arr[i]; else { int pos=upper_bound(ans+1,ans+len+1,arr[i])-ans;//****ei严格 ans[pos] = arr[i]; } } printf("Case #%d:\n%d\n",cnt++,n-len); } return 0; }