SW练习_P1233 木棍加工_变形LIS_sw圆棒受压变形-CSDN博客

本文链接：https://blog.csdn.net/mush_me/article/details/107192100

本文探讨了如何利用dilworth定理解决木棍加工问题，重点在于理解下降子序列的最小划分与最长不下降子序列长度之间的关系。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

从dilworth定理中，我们可知，下降子序列的最小划分等于最长不下降子序列的长度
主要是这个定理


package com.company.luogu;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class P1233 {
//从dilworth定理中，我们可知，下降子序列的最小划分等于最长不下降子序列的长度
    public static void main(String[] args) throws Exception{
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(reader.readLine());
        int N=Integer.parseInt(st.nextToken());//棍子的个数
        Node1233[] nodes=new Node1233[N];
        st=new StringTokenizer(reader.readLine());
        for (int i = 0; i <N ; i++) {
            nodes[i]=new Node1233(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(nodes);
        int[] arrs=new int[nodes.length];
        for (int i = 0; i < nodes.length; i++) {
            arrs[i]=nodes[i].w;
        }
        System.out.println(LIS(arrs));
        reader.close();
    }
    public static int LIS(int[] arrs){
        //int[] len=new int[arrs.length];
        LinkedList<Integer> list=new LinkedList<Integer>();
        list.add(arrs[0]);
        for (int i = 1; i <arrs.length ; i++) {
            if(arrs[i]>list.getLast()){
                list.add(arrs[i]);
            }else{
                int index=searchList(list,arrs[i]);
                list.set(index,arrs[i]);
            }
            //len[i]=list.size();
        }
        return list.size();
    }
    private static int searchList(LinkedList<Integer> list, int a) {
        int low=0;
        int high=list.size()-1;
        while(low<=high){
            int mid=(low+high)/2;
            if(list.get(mid)==a){
                return mid;
            }else if(list.get(mid)>a){
                high=mid-1;
            }else{
                low=mid+1;
            }
        }
        return low;
    }
}
class Node1233 implements Comparable<Node1233>{
    int l;//长度
    int w;//宽度
    public Node1233(int l, int w) {
        this.l = l;
        this.w = w;
    }
    @Override
    public int compareTo(Node1233 o) {//按照从大到小排序
        if(this.l!=o.l){
            return o.l-this.l;
        }else{
            return o.w-this.w;
        }
    }
}