拼多多笔试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);


        }
    }
}



全部评论
哥们 咋理解这道题目呢
点赞 回复 分享
发布于 2024-06-17 22:11 安徽

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务