验证中...
Languages: Java
Categories: 算法分析
Latest update 2019-09-11 20:27
gistfile1.txt
Raw Copy
import java.io.*;
import java.util.*;
/**
* Welcome to vivo !
*/
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String inputStr = br.readLine();
String[] input = inputStr.split(" ");
int totalDisk = Integer.parseInt(input[0]);
int totalMemory = Integer.parseInt(input[1]);
List<Service> services = parseServices(input[2].split("#"));
int output = solution(totalDisk, totalMemory, services);
System.out.println(output);
}
private static int solution(int totalDisk, int totalMemory, List<Service> services) {
// TODO Write your code here
int[][] dp = new int[totalDisk+1][totalMemory+1];
for (int i=0; i<totalDisk+1; i++) {
for (int j=0; j<totalMemory+1; j++) {
dp[i][j] = -2;
}
}
solution(totalDisk, totalMemory, services);
for (int i=0; i<totalDisk+1; i++) {
for (int j=0; j<totalMemory+1; j++) {
dp[i][j] = -2;
}
} boolean[] used = new boolean[services.size()];
return solution(totalDisk, totalMemory, services, dp, used);
}
private static int solution(int totalDisk, int totalMemory, List<Service> services, int[][] dp, boolean[] used) {
if (totalDisk < 0 || totalMemory < 0) {
return -1;
}
if (totalDisk == 0 || totalMemory == 0) {
return 0;
}
int ret = Integer.MIN_VALUE;
for (int i=0; i<services.size(); i++) {
if (used[i]) {
continue;
}
if (totalDisk-services.get(i).disk < 0 || totalMemory-services.get(i).memory < 0) {
continue;
}
if (dp[totalDisk-services.get(i).disk][totalMemory-services.get(i).memory] == -1) {
continue;
}
if (dp[totalDisk-services.get(i).disk][totalMemory-services.get(i).memory] != -2) {
ret = Math.max(ret, dp[totalDisk-services.get(i).disk][totalMemory-services.get(i).memory]+services.get(i).users);
} else {
used[i] = true;
ret = Math.max(ret, solution(totalDisk-services.get(i).disk, totalMemory-services.get(i).memory, services, dp, used));
used[i] = false;
}
}
if (ret == -1 || ret == Integer.MIN_VALUE) {
dp[totalDisk][totalMemory] = -1;
return -1;
} else {
dp[totalDisk][totalMemory] = ret;
return ret;
}
}
private static List<Service> parseServices(String[] strArr) {
if (strArr == null || strArr.length == 0) {
return new ArrayList<Service>(0);
}
List<Service> services = new ArrayList<>(strArr.length);
for (int i = 0; i < strArr.length; i++) {
String[] serviceArr = strArr[i].split(",");
int disk = Integer.parseInt(serviceArr[0]);
int memory = Integer.parseInt(serviceArr[1]);
int users = Integer.parseInt(serviceArr[2]);
services.add(new Service(disk, memory, users));
}
return services;
}
static class Service {
private int disk;
private int memory;
private int users;
public Service(int disk, int memory, int users) {
this.disk = disk;
this.memory = memory;
this.users = users;
}
public int getDisk() {
return disk;
}
public void setDisk(int disk) {
this.disk = disk;
}
public int getMemory() {
return memory;
}
public void setMemory(int memory) {
this.memory = memory;
}
public int getusers() {
return users;
}
public void setusers(int users) {
this.users = users;
}
}
}

Comment list( 0 )

You need to Sign in for post a comment

Help Search