AcWing 2704. 音量调节
原题链接
困难
作者:
两生
,
2024-01-30 17:02:34
,
所有人可见
,
阅读 37
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static StreamTokenizer stmInput = new StreamTokenizer(br);
static int N = 55, M = 1010;
static int a[] = new int[N];
static boolean f[][] = new boolean[N][M];
static int n, m, s;
public static int readInt() throws IOException{
stmInput.nextToken();
return (int) stmInput.nval;
}
public static void solve() throws IOException{
n = readInt();
s = readInt();
m = readInt();
for(int i = 1; i <= n; i++) {
a[i] = readInt();
}
// f[i][j]表示在前i个音量中选, 是否能凑出音量为j
// 初始时存在音量为s
f[0][s] = true;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++) {
// 1. 加上当前音量a[i]
if(j >= a[i]) f[i][j] |= f[i - 1][j - a[i]];
// 2. 减去当前音量a[i]
if(j + a[i] <= m) f[i][j] |= f[i - 1][j + a[i]];
}
}
int res = -1;
for(int i = 0; i <= m; i++) {
if(f[n][i]) res = i;
}
pw.println(res);
}
public static void main(String[] args) throws IOException {
int T = 1;
while(T-- != 0){
solve();
}
pw.flush();
pw.close();
br.close();
}
}