拼多多笔试6.16

public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0){
            int N=scanner.nextInt();
            int[] prices = new int[N+1];
            for(int i=1;i<=N;i++) {
                prices[i]=scanner.nextInt();
            }
            int[][] dp=new int[N+1][N+1];
            int[] chances=new int[N+2];
            for(int i=0;i<=N;i++) {
                Arrays.fill(dp[i],Integer.MAX_VALUE-100);
            }
            dp[0][0]=0;
            int sum=0;
            for(int i=1;i<=N;i++) {
                sum+=prices[i];
                if(chances[i]==0)
                chances[i]=chances[i-1];
                if(sum>=100){
                    chances[i+1]=chances[i]+1;
                    sum-=100;
                }
            }
            for(int i=1;i<=N;i++) {
                for(int j=chances[i];j>=0;j--){
                    dp[i][j] = dp[i-1][j]+prices[i];
                    if(j-1>=0){
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1]);
                    }
                }
                if(chances[i]!=chances[i-1])
                    dp[i][chances[i]] = Math.min(dp[i][chances[i]], dp[i-1][chances[i-1]]);
            }
            int ans=dp[N][chances[N]];
            System.out.println(ans);


        }
    }
}