SRM 515 DIV 二 1000P

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 t
	double 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/P
		for (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;
	}
}