【lis】洛谷P3365 改造二叉树

题面在这里

因为要满足\(a_i-a_j\ge i-j\)\(a_i-i\ge a_j-j\)

那么对\(\{ a_i-i \}\)这个序列做最长不降子序列就好了

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;

const int maxn=100005,maxe=maxn;
int n,m,w[maxn],a[maxn],lnk[maxn][2],g[maxn];
void dfs(int x){
if (lnk[x][0]) dfs(lnk[x][0]);
a[++m]=w[x];
if (lnk[x][1]) dfs(lnk[x][1]);
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&w[i]);
for (int i=2,fa,s;i<=n;i++) scanf("%d%d",&fa,&s),lnk[fa][s]=i;
dfs(1); for (int i=1;i<=n;i++) a[i]-=i;
int len=1;g[1]=a[1];
for (int i=2;i<=n;i++)
if (g[len]<=a[i]) g[++len]=a[i];else *upper_bound(g+1,g+1+len,a[i])=a[i];
printf("%d",n-len);
return 0;
}