复旦计算机2021机试

明天就要机试了，目前只做了2020年的题目，今天准备把2017-2021做完。

第一题看到很多思路是建树。但是完全二叉树可以用数组来表示，这时可以使用一个dp数组进行动态规划，记录到第n个数时最大的数是多少即可。

import java.util.Scanner;
public class A_2021 {
    static Scanner scanner=new Scanner(System.in);
    public static void main(String[] args) {
        String s = scanner.nextLine();
        String[] split = s.split(",");
        //num多出一个0位置 这是为了后面方便计算父元素节点
        int[] num=new int[split.length+1];
        int[] dp=new int[split.length+1];
        int i=1;
        int result=1;//根节点一定是关键节点
        for (String s1 : split) {
                if(!s1.equals("null")){
                    num[i++]=Integer.parseInt(s1);
                }else{
                    num[i++]=Integer.MIN_VALUE;
                }
        }
        dp[1]=num[1];
        for(i=2;i 
 第二题 
 
第二题比第一题还要简单，是最基础的动态规划问题，直接上代码。
 
import java.util.Scanner;
public class B_2021 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int dp[]=new int[n];
        if(n==1){
            System.out.println(1);
            return;
        }
        dp[0]=1;
        dp[1]=2;
        for(int i=2;i 
第三题 
 
这题出的很好，由于序列中本身都是非负数，所以如果出现负数一定是对其取负。期望值=正数+负数，总值=正数-负数，所以期望值+总值为两倍的正数值，这就化解成了背包问题，从这些数中取出指定数有多少种取法。需要用一个二维dp数组来解决。
 
对于每一个数，都有取和不取两种选项，dp[i][j]代表在前i个数中，取到j这个数有多少种方法，dp的最左边一列表示取0的方法数，都是1。最后返回dp[m-1][n]
 
import java.util.Scanner;
public class C_2021 {
    static Scanner scanner=new Scanner(System.in);
    public static void main(String[] args) {
        //读取数据 计算total
        String s = scanner.nextLine();
        int e=scanner.nextInt();
        String[] split = s.split(",");
        int[] num=new int[split.length];
        int total=0;
        for(int i=0;i=num[i]){
                        dp[i][j]=dp[i-1][j]+dp[i-1][j-num[i]];
                    }else{
                        dp[i][j]=dp[i-1][j];
                    }
                }
            }
        }
        
        //输出结果
        System.out.println(dp[split.length-1][E]);

    }
}