[UVA][dp] 12018 - Juice Extractor
Juice Extractor
| Juice Extractor |
Jerry loses himself in the interesting game: Fruit Ninja. Fruit Ninja is a game of iPhone and iPad in which the players cut the fruits coming from the bottom of the screen and gain the bonus from cutting more than two fruits with a single slice. Once a fruit is cut, it breaks into small pieces and cannot be cut any more.
After months of training, he becomes pro of this game. Actually, he can cut all the fruits on the screen at any time. Jerry also has a bad habit that he has no willing to leave some fruits for the future cutting. In the other words, after Jerry cuts the fruits, all the fruits on the screen breaks and no one left. That is why all his friends call him `Juice Extractor'.
Now he only consider about the bonus, when he cuts more than two fruits, he can gain some bonus scores as same as the number of fruits he slice at that time. For example, if Jerry cuts 4 fruits with a single slice, he can get 4 scores from this slice.
After Jerry gets the fruit schedule, he knows the appearing time and the disappearing time for every single fruit. He can only cut a fruit into pieces between its appearing time and disappearing time inclusive. He wants to know the maximum possible bonus scores he can receive.
Input
There are several test cases; the first line of the input contains a single integer T, denoting the number of the test cases. (T
200)
For each test case, the first line contains an integer N, denoting the total
number of fruits. (
1N1000)
The next N lines, each line describe a fruit. For each line, there are two
integers Xi and Yi, where Xi is the appearing time of the fruit and Yi is the
disappearing time of this fruit. (
0XiYi1000000000)
Output
For each test case, output a single integer denoting the maximum scores that Jerry could possibly gain. See the sample for further details.
Sample Input
1 10 1 10 2 11 3 12 4 13 13 14 14 15 13 19 20 22 21 23 22 24
Sample Output
Case #1: 10
題目描述：
給定每個水果出現在螢幕的起始時間與離開時間，三個同時被切到時，才能計算得分(等於當前被切的個數)
問整場遊戲下來， Jerry 最多可以得幾分 (可以切很多次，並不是求一刀最多可得多少分)。
但 Jerry 有一個壞習慣，一刀下去，並不會保留部分水果給下一次切，而會把所有水果都給切了。
(就是這個壞習慣，讓我 WA 好幾次。這太邪惡了)
題目解法：
按照起始時間做排序後，枚舉這一刀最後一個被切的水果與這一刀第一個時間點的水果，然後進行轉移。
特別小心它的壞習慣，同一個時間出來的水果，要切就全部都要切下去。
留給後面的計算分數，會錯的。
即將同一個時間出來的水果分成一刀涵蓋前面的，另一個保留給後面的一刀，如果後面根本無法湊滿三個，那麼是會錯的。
dp[i] = max(dp[j]+cut_count[j->i]), j <= i
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
struct E {
int l, r;
bool operator<(const E &a) const {
if(l != a.l)
return l < a.l;
return r < a.r;
}
};
int main() {
int t, n, i, j;
int cases = 0;
scanf("%d", &t);
E D[1005];
while(t--) {
scanf("%d", &n);
for(i = 1; i <= n; i++)
scanf("%d %d", &D[i].l, &D[i].r);
sort(D+1, D+1+n);
int dp[1005] = {}, ret = 0;
for(i = 1; i <= n; i++) {
int combo = 0;
if(i != n && D[i].l == D[i+1].l)
continue;
for(j = i; j >= 1; j--) {
if(D[j].r >= D[i].l)
combo++;
if(combo >= 3)
dp[i] = max(dp[i], dp[j-1]+combo);
else
dp[i] = max(dp[i], dp[j-1]);
}
ret = max(ret, dp[i]);
}
printf("Case #%d: %d\n", ++cases, ret);
}
return 0;
}
/*
20
20
48 69
33 76
27 62
2 9
42 63
10 24
0 15
13 54
10 52
40 48
45 55
17 35
22 52
42 78
27 42
44 58
39 68
17 61
42 64
29 69
*/