简单错误记录_马戏团_合唱团

简单错误记录

马戏团

import java.util.*;
class Node implements Comparable<Node>{
    public int w;
    public int h;
    public Node(int w,int h){
        this.w = w;
        this.h = h;
    }
    public int compareTo(Node obj){
        int ret = this.w - obj.w;
        if(ret==0){//体重相同，身高降序！
            return obj.h - this.h;
        }
        //按照身高升序排序！
        return ret;
    }
}
public class Main{
    public static int getMathLen(Node[] nodes,int n){
        //按体重排升序，体重相同，身高降序！
        Arrays.sort(nodes);
        //动归求最长递增子序列！
        //f(i):以i结尾的最长递增子序列！
        // f(i) = math(f(j)+1,f(i)) (j<i)&& nodes[j].h<=nodes.h;
        //初始化 f(i) = 1;//以i结尾的子序列至少长度为1
        //返回结果 Math(f(i)) 
        int result = 0;
        int[] dp = new int[n];
        for(int i = 0;i<n;i++){
            dp[i] = 1;
        }
        for(int i = 1;i<n;i++){
            for(int j = 0;j<i;j++){
                if(nodes[j].h <= nodes[i].h){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
            result = Math.max(dp[i],result);
        }
        return result;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            Node[] nodes = new Node[n];
            for(int i = 0;i< n;i++){
                sc.nextInt();
                nodes[i] = new Node(sc.nextInt(),sc.nextInt());
            }
            System.out.println(getMathLen(nodes,n));
        }
    }
}

合唱团

import java.util.*;
public class Main{
    public static long getMaxVal(long[] arr,int n,int k,int d){
         long[][] MaxVal = new long[n+1][k+1];
         long[][] MinVal = new long[n+1][k+1];
        //初始化：
        for(int i = 1;i<=n;i++){
            MaxVal[i][1] = MinVal[i][1] = arr[i];
        }
        long result = MaxVal[1][1];
        //状态转移：
        for(int i = 2;i<=n;i++){
            for(int j = 2;j<= k;j++){
                //i-d <= m <= i-1;
               for(int m = Math.max(1,i-d);m<=i-1;m++){
                   MaxVal[i][j] = Math.max(MaxVal[i][j],
                                 Math.max(MaxVal[m][j-1]*arr[i],MinVal[m][j-1]*arr[i]));
                    MinVal[i][j] = Math.min(MinVal[i][j],
                                 Math.min(MaxVal[m][j-1]*arr[i],MinVal[m][j-1]*arr[i]));
               }
            }
           result = Math.max(MaxVal[i][k],result);
        }
        return result;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            long[] arr = new long[n+1];
            for(int i = 1;i<=n;i++){
                arr[i] = sc.nextInt();
            }
            int k = sc.nextInt();
            int d = sc.nextInt();
            System.out.println(getMaxVal(arr,n,k,d));
        }
    }
}