SRM 515 DIV 2 1000P
很喜欢这题，但不会做，看了代码还是不完全理解这个DP，叹叹。
顺便求题解^_^
1000P Problem
你有一个商品，有两个客人，数据格式都为"T1,C1,P1 T2,C2,P2 ... TN,CN,PN"，T表示时间，C表示价格，P表示概率，比如"8,10,50"表示有50%的可能性这个客户8点来出价10元，每小时最多只有一个客人来。
求最大期望值。
1000P Solution
来自官方题解
public class NewItemShopTwo {int[][] T = new int[2][25];int[][] C = new int[2][25];double[][] P = new double[2][25];// the expected profit if we know that he has not come before time tdouble getExpected(int customer, int index) {double p = 1;for (int i = 0; i < index; i++)p -= P[customer][i];double ret = 0;for (int i = index; P[customer][i] > -1; i++)ret += C[customer][i] * P[customer][i]/p;return ret;}public double getMaximum(String[] customers) {// Read in the values of the customers to T/C/Pfor (int i = 0; i < customers.length; i++) {Arrays.fill(P[i], -1);String[] tmp = customers[i].split(" ");for (int j = 0; j < tmp.length; j++) {String[] t = tmp[j].split(",");T[i][j] = Integer.valueOf(t[0]);C[i][j] = Integer.valueOf(t[1]);P[i][j] = Integer.valueOf(t[2])/100.0;}}double ret = 0, p1 = 1, p2 = 1;int t1 = 0, t2 = 0;for (int h = 0; h < 24; h++) {if (T[0][t1] == h) {ret += (P[0][t1]/p1)*p1*p2*Math.max(C[0][t1], getExpected(1, t2));p1 -= P[0][t1];t1++;} else if (T[1][t2] == h) {ret += (P[1][t2]/p2)*p1*p2*Math.max(C[1][t2], getExpected(0, t1));p2 -= P[1][t2];t2++;}}return ret;}}