https://ac.nowcoder.com/acm/contest/329/H
JAVA版本一
题解:
std
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
new Main();
}
Main() throws Exception {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
int n=in.nextInt();
int[]a=new int[n+1],p=new int[101];
BigInteger[] t=new BigInteger[n+1],P=new BigInteger[101],dp=new BigInteger[201];
final BigInteger i10000=BigInteger.valueOf(10000),i100=BigInteger.valueOf(100);
for(int i=1;i<=n;i++){
a[i]=in.nextInt();
t[i]=BigInteger.valueOf((100+in.nextInt())*(100-in.nextInt()));
}
for(int i=1;i<=100;i++) {
p[i]=in.nextInt();
P[i] = BigInteger.valueOf(p[i] * 2);
}
dp[1]=BigInteger.valueOf(1000);
dp[0]=BigInteger.ZERO;
for(int i=2;i<=200;i++){
if((i&1)==0&&p[i>>1]>50)
dp[i]=dp[i-1].multiply(P[i>>1]).divide(i100);
else dp[i]=dp[i-1];
if((i&1)!=0)
for(int j=1;j<=n;j++){
if(i-2*a[j]+1<0)continue;
dp[i]=dp[i].max(dp[i-2*a[j]+1].multiply(t[j]).divide(i10000));
}
}
out.println(dp[200].mod(BigInteger.valueOf(1000000007)));
out.flush();
}
}
class InputReader {
private BufferedReader reader;
private char[] buf;
private int len, now;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
buf = new char[1024];
len = 0;
now = 0;
}
public String next() throws IOException {
if (!hasNext()) throw new NullPointerException();
StringBuilder sb = new StringBuilder();
while (!isSpaceChar(buf[now])) {
sb.append(buf[now]);
if (!move()) break;
}
return sb.toString();
}
public int nextInt() throws IOException {
if (!hasNext()) throw new NullPointerException();
boolean x = false;
if (buf[now] == '-') {
x = true;
if (!move()) throw new NumberFormatException();
}
int ans = 0;
while (!isSpaceChar(buf[now])) {
if (isNum(buf[now])) ans = ans * 10 + buf[now] - '0';
else throw new NumberFormatException();
if (!move()) break;
}
return (x ? -1 : 1) * ans;
}
public String nextLine() throws IOException {
if (!hasNextLine()) throw new NullPointerException();
StringBuilder sb = new StringBuilder();
while (buf[now] != '\n') {
sb.append(buf[now]);
if (!move()) return sb.toString();
}
now++;
return sb.toString();
}
public long nextLong() throws IOException {
if (!hasNext()) throw new NullPointerException();
boolean x = false;
if (buf[now] == '-') {
x = true;
if (!move()) throw new NumberFormatException();
}
long ans = 0;
while (!isSpaceChar(buf[now])) {
if (isNum(buf[now])) ans = ans * 10 + buf[now] - '0';
else throw new NumberFormatException();
if (!move()) break;
}
return (x ? -1 : 1) * ans;
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public int nextHexInt() throws IOException {
if (!hasNext()) throw new NullPointerException();
boolean x = false;
if (buf[now] == '-') {
x = true;
if (!move()) throw new NumberFormatException();
}
int ans = 0;
while (!isSpaceChar(buf[now])) {
if (isHex(buf[now])) ans = ans * 16 + toHex(buf[now]);
else throw new NumberFormatException();
if (!move()) break;
}
return (x ? -1 : 1) * ans;
}
public char nextChar() throws IOException {
if (!hasNext()) throw new NullPointerException();
char tmp = buf[now];
move();
return tmp;
}
public boolean hasNext() throws IOException {
return skip();
}
public boolean hasNextLine() throws IOException {
return now < len || refill();
}
private boolean move() throws IOException {
now++;
return hasNextLine();
}
private boolean skip() throws IOException {
if (!hasNextLine()) return false;
while (isSpaceChar(buf[now])) {
if (!move()) return false;
}
return true;
}
private boolean isSpaceChar(char c) {
return !(c >= 33 && c <= 126);
}
private boolean isNum(char c) {
return c >= '0' && c <= '9';
}
private boolean isHex(char c) {
return c >= '0' && c <= '9' || c >= 'A' && c <= 'F';
}
private int toHex(char c) {
if (c >= '0' && c <= '9') return c - '0';
else return c - 'A' + 10;
}
private boolean refill() throws IOException {
len = reader.read(buf);
now = 0;
return len > 0;
}
}