HDU - 5256 序列變換 【LIS變形】

傳送們：​​5256​​

他讓求至少可以改變幾個數讓他們單調遞增

我們可以處理一下-.-讓每一個數都減去i（這樣在後面求出的最長遞增子序列的每幾個數之間都有相應的空位使他變過來）

然後求最長遞增子序列就可以啦-.-

如：

4

2 3 3 4

變為

2 2 1 1

最長遞增子序列為2，2 或1 ，1---

我們就可以變為2 3 4 5或1 2 3 4（變2個（4-2））

再如：

4

2 3 3 5

變為：

2 2 1 2

最長遞增子序列為2 ，2，2

我們就把那個1也變為2--（變1個（4-3））

然後就是

2 2 2 2

還原為

2 3 4 5

#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
int a[100100],shu[100100],kp;
void s(int xx)
{
  int n;scanf("%d",&n);
  for (int i=0;i<n;i++)
  {
    scanf("%d",&shu[i]);
    shu[i]-=i;
  }
  kp=0;
  a[kp++]=shu[0];
  for (int i=1;i<n;i++)
    if (shu[i]>=a[kp-1])
      a[kp++]=shu[i];
    else
      a[upper_bound(a,a+kp,shu[i])-a]=shu[i];
  printf("Case #%d:\n%d\n",xx,n-kp);
}
int main()
{
  int t;scanf("%d",&t);
  for (int xx=1;xx<=t;xx++)
  s(xx);
  return 0;
}