美团笔试

100 100 100 13.33 0

第四题dp做出来了，但是考试的时候忘记将dp和temp声明为long类型，还不知道哪里错了

下午小红书第三题也是没有用long没过，这次长记性了

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n+1];
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
            sum += a[i];
        }
        if(n == 1) {
            System.out.println(0);
            return;
        }
        long[][] dp = new long[n+1][sum+1];
        for (int i = 2; i < sum + 1; i++) {
            if(i < a[1] + a[2]) {
                if(i <= a[1] && i <= a[2]) {
                    dp[2][i] = i - 1;
                } else if(i == Math.max(a[1], a[2])) {
                    dp[2][i] = i - 2;
                } else if(i < Math.max(a[1], a[2]) && i > Math.min(a[1], a[2])) {
                    dp[2][i] = i - 2;
                } else {
                    dp[2][i] = i - 3;
                }
            } else if (i == a[1] + a[2]) {
                dp[2][i] = i - 2;
            } else {
                dp[2][i] = i - 3;
            }
        }
        for (int i = 3; i < n+1; i++) {
            long temp = 0;
            for(int j = 2; j < sum+1; j++) {
                if(j < i) continue;
                temp += dp[i-1][j-1];
                if(j >= a[i])
                    dp[i][j] = temp - dp[i-1][j-a[i]];
                else dp[i][j] = temp;
                dp[i][j] %= 1000000007;
            }
        }

        System.out.println(dp[n][sum]);
    }
}