Create a gist now

Instantly share code, notes, and snippets.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
public class Main {
public static void main(String[] args) throws ScriptException {
int requiedNumOfMember = 0;
int numOfCompany = 0;
int numOfMemberIfUseAll = 0;
List<Integer> membersOfCompany = new ArrayList<>();
List<Integer> costOfCompany = new ArrayList<>();
// 入力データの読み込み。
try (Scanner scanner = new Scanner(System.in)) {
requiedNumOfMember = scanner.nextInt();
numOfCompany = scanner.nextInt();
for (int i = 0; i < numOfCompany; i++) {
membersOfCompany.add(scanner.nextInt());
numOfMemberIfUseAll += membersOfCompany.get(i);
costOfCompany.add(scanner.nextInt());
}
};
ScriptEngine engine = new ScriptEngineManager().getEngineByName("nashorn");
String script
= "var requiedNumOfMember = " + requiedNumOfMember + ";\n"
+ "var numOfCompany = " + numOfCompany + ";\n"
+ "var numOfMemberIfUseAll = " + numOfMemberIfUseAll + ";\n"
+ "var membersOfCompany = " + membersOfCompany + ";\n"
+ "var costOfCompany = " + costOfCompany + ";\n"
+ "var leastCostByNumOfMember = []; \n"
+ "// 先頭以外を未処理 (-1)で初期化\n"
+ "leastCostByNumOfMember[0] = 0\n"
+ "for (var i = 0; i < numOfMemberIfUseAll; i++) {\n"
+ " leastCostByNumOfMember[leastCostByNumOfMember.length] = -1;\n"
+ "}\n"
+ "for (var i = 0; i < numOfCompany; i++) {\n"
+ " // i 番目の会社の処理\n"
+ " for (var j = numOfMemberIfUseAll; j >= membersOfCompany[i]; j--) {\n"
+ " // 全人数 から、この会社の人数まで順に処理。\n"
+ " // leastCostByNumOfMember[j]に対してi 番目の会社を使うとより安くなるなら更新\n"
+ " var costWithoutCompanyJ = leastCostByNumOfMember[j - membersOfCompany[i]];\n"
+ " if (costWithoutCompanyJ >= 0) {\n"
+ " var newCost = costWithoutCompanyJ + costOfCompany[i];\n"
+ " if (leastCostByNumOfMember[j] < 0 || leastCostByNumOfMember[j] > newCost) {\n"
+ " //未設定あるいはより安くなるなら更新\n"
+ " leastCostByNumOfMember[j] = newCost;\n"
+ " }\n"
+ " }\n"
+ " }\n"
+ "}\n"
+ "var j = -1;\n"
+ "for (var i = requiedNumOfMember; i <= numOfMemberIfUseAll; i++) {\n"
+ " if (j < 0 || (leastCostByNumOfMember[i] >= 0 && j > leastCostByNumOfMember[i])) {\n"
+ " j = leastCostByNumOfMember[i];\n"
+ " }\n"
+ "}\n"
+ "print(j);\n";
engine.eval(script);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment