2015
04-16

Raining

There are N mountains represented by N Isosceles triangles above ground. We can assume that every adjacent mountain can shape a valley. When it rains, the rain will form a plane in the valley. Now let’s make things a little easier by drawing the vertical profile of the actual mountains. You can get more details from the below figure.

When it rains, the quantity of water is proportional to the time that is raining and the length of the plane by which some valley can receive the water (in the figure 1, “l1” is the length of the plane). In the figure 1, v means the velocity of the rain (please see the figure for more details for the formula of the rain). If a valley is filled with rain, the water will overflow. According to the shape of the mountain, the water may flow to the left, or to the right. You can assume that the height of the different mountains are different. This outflow of water will fill the valley next to the current valley. You can get the more details from the Figure 2.

You will get the information of the mountain. Please output the time during which the mountains can be filled by the rain. After the time, the quantity of the water will not increase even if it still rains.

The first line of an input file consists of a single number denoting the number of test cases in the file. The number of cases is not more than 20.
For each test case, the input format is as follows. The first line gives two integers N and V( 1<=N<=5000, 20<=V<=200). N is the number of the mountains and V is the velocity of the rain. For the next n lines, the ith line gives three integers Li, Ri, Hi( 0<=Li<Ri<=10^9, 1<=Hi<=2500000, i=1, 2, … , N). li is the coordinate of the left bottom point of the ith mountain. And the ri is the right one. hi is the height of the ith mountain. You can assume that Li<=Ri-1.We guarantee that the valley exists between every two adjacent mountains. You can assume that the left coordinate of the i+1th mountain is strictly larger than the corresponding one of the ith mountain. Please mind that there may be such conditions like the figure 3.

The first line of an input file consists of a single number denoting the number of test cases in the file. The number of cases is not more than 20.
For each test case, the input format is as follows. The first line gives two integers N and V( 1<=N<=5000, 20<=V<=200). N is the number of the mountains and V is the velocity of the rain. For the next n lines, the ith line gives three integers Li, Ri, Hi( 0<=Li<Ri<=10^9, 1<=Hi<=2500000, i=1, 2, … , N). li is the coordinate of the left bottom point of the ith mountain. And the ri is the right one. hi is the height of the ith mountain. You can assume that Li<=Ri-1.We guarantee that the valley exists between every two adjacent mountains. You can assume that the left coordinate of the i+1th mountain is strictly larger than the corresponding one of the ith mountain. Please mind that there may be such conditions like the figure 3.

2

2 3
0 2 1
1 5 2

5 3
0 26 37
17 59 35
48 81 79
77 123 77
106 212 33

0.042
11.384

1. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

2. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？