【区间 dp】B009_JM_同桌的你（分组后 LIS / 二分优化）

一、Problem

输入

第一行输入一个整数 N，表示有 N 对同桌。

第二行输入2N2N个整数，表示从左到右每一张桌子上同学的成绩 $a_i$ai​

输出

输出一个整数表示最少需要几个同学出列调整。

3
16 2 1 7 5 10

2

二、Solution

方法一：dp

难点在于转化问题：因为两个人在同一张桌子上，故两个人的桌子序号是一样的，比如成绩

16,2,1,7,5,10，对应的排名如下
1,5,6,3,4,2，对应的桌子号如下
1,2,1,3,3,2	

需求是将拥有同桌子号的同学变成紧挨着的最少步数，即：
1,1,2,2,3,3

需要移动的人数 = tot - 不需要移动的人数

不需要移动的人一定是构成了升序子结构，而需要移动的人一定是干扰了别人。

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{
	static class Solution {
		void init() {
			Scanner sc = new Scanner(new BufferedInputStream(System.in));
			int n = sc.nextInt(), tot = 2 * n;
			int a[] = new int[tot], dp[] = new int[tot];
			Integer[] b = new Integer[tot];
			for (int i = 0; i < tot; i++) {
				b[i] = a[i] = sc.nextInt();
			} 
			Arrays.sort(b, (e1, e2) -> e2 - e1);
			for (int i = 0; i < tot; i++) 
			for (int j = 0; j < n; j++){
				if (a[i] == b[j] || a[j] == b[tot-j-1])
					a[i] = j;
			}
			Arrays.fill(dp, 1);
			for (int i = 1; i < tot; i++)
			for (int j = 0; j < i; j++) {
				if (a[j] <= a[i])
				    dp[i] = Math.max(dp[i], dp[j]+1);
			}
			int max = 0;
		    for (int i = 0; i < tot; i++)
		        max=  Math.max(max, dp[i]);
			System.out.println(tot-max);
		}
	}
    public static void main(String[] args) throws IOException {  
        Solution s = new Solution();
		s.init();
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$O(n2)，
• 空间复杂度：$O(n)$O(n)，

---

方法二：二分优化

LIS 问题，可以用二分加速 dp 的第二层循环，也就是优化掉求 $[0, i]$[0,i] 位置的子 LIS 的问题。

代办把…

复杂度分析

• 时间复杂度：$O(nlogn)$O(nlogn)，
• 空间复杂度：$O(n)$O(n)，