洛谷P2392 kkksc03考前临时抱佛脚--Java解法

川长思鸟来 2022-10-27 12:07 4阅读 0赞

# 洛谷P2392 kkksc03考前临时抱佛脚–Java解法 #

[题目链接][Link 1]

## 题目描述 ##

略

## 解题思路 ##

### 语言描述 ###

个人认为本题目题意比较清晰，我们只需分别求得做每一科目的所需的最短时间，然后4科最短时间加起来即为我们需要的答案。  
对于求每一科目的最短时间，我们可以将问题转化成**0-1背包**问题，这科所有题目时间和的一半即为背包的容量，而每个题解需要的时间即为物品，然后我们遍历所有物品之后能让背包中装的物品的东西体积（时间）尽可能的多即可，然后总时间减去最大时间即为我们这科做完的最短时间。

### 代码描述 ###

import java.io.*;
    import java.util.*;
    public class Main {
        
    	static int[] num;
    	public static void main(String[] args) throws IOException {
        
    		Scanner sc=new Scanner(System.in);
    		PrintWriter pr=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    		int[][] times=new int[4][];
    		for(int i=0;i<4;i++) {
        
    			int n=sc.nextInt();
    			times[i]=new int[n];
    		}
    		for(int i=0;i<4;i++) {
        
    			for(int j=0;j<times[i].length;j++) {
        
    				times[i][j]=sc.nextInt();
    			}
    		}
    		int res=0;
    		int sum;
    		for(int i=0;i<4;i++) {
        
    			sum=Arrays.stream(times[i]).sum();
    			int sum1=sum;
    			sum=sum>>1;
    			int[] dp=new int[sum+1];
    			for(int j=0;j<times[i].length;j++) {
        
    				for(int k=sum;k>=times[i][j];k--) {
        
    					dp[k]=Math.max(dp[k], dp[k-times[i][j]]+times[i][j]);
    				}
    			}
    			res+=(sum1-dp[sum]);
    		}
    		pr.println(res);
    		pr.flush();
    		return;
    	}
    }

[Link 1]: https://www.luogu.com.cn/problem/P2392