思路
有n辆车,我们可以计算出把这些车洗完的总时间为sum(两台洗车器时间加起来的总时间),我们假设某一台洗车器
洗车时间为j,那么另一台的花费时间就是sum-j。而本地的ans = Math.min(ans, Math.max(j, sum-j)),这里的j肯定
可以取值[0, sum]范围内的部分数,但是为了求解ans,我们需要知道这些数具体有哪些。于是,我们可以抽象出问题:
对于n个数 a[1]、a[2]…a[n]可以凑出哪些数?
f[i][j]表示对于前i辆车能否选出若干车辆刚好花费j时间洗完,而对于f[i][j]我们关注第i辆车选(f[i-1][j])或者不选f[i-1][j-a[i]],
只要上述两种状态有一种为true,f[i][j]就是可以实现的状态
代码
import java.io.*;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = 110, M = 100010;
static boolean[][] f = new boolean[N][M];
static int[] a = new int[N];
public static void main(String[] args)throws IOException{
int n = nextInt();
int sum = 0;
for(int i=1; i<=n; i++){
a[i] = nextInt();
sum += a[i];
}
f[0][0] = true;
for(int i=1; i<=n; i++){
for(int j=0; j<=sum; j++){
f[i][j] = f[i-1][j];
if(j>=a[i]) f[i][j] |= f[i-1][j-a[i]];
}
}
int ans = Integer.MAX_VALUE;
for(int i=0; i<=sum; i++){
if(f[n][i]) ans = Math.min(ans, Math.max(i, sum-i));
}
out.println(ans);
out.flush();
out.close();
}
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
}