UVA - 12018 Juice Extractor(dp)

Posted on | In , ,

思路

首先对水果按出现时间为第一关键字，消失时间为第二关键字来排序。dp[i]为当物品i出现时将它及它之前的水果全切完的最大价值。转移时第一重循环顺序枚举物品，设置一个计数器记录从i水果到第二重循环的那个水果之间有几个还在空中。第二重循环从当前物品往前找，每当发现其还在空中时计数器++。然后就是dp[i]=max(dp[i],dp[j-1]+cnt>2?cnt:0)来转移。这里要注意的一点是如果左端点重合的区间要取数组中最左边的一个区间，因为题意要求我们对在空中的水过一次切完不能有剩，不这样做的话可能会让结果的答案变大。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define ms(a,val) memset(a,val,sizeof(a))
#define ll long long
#define INF 0x7fffffff

using namespace std;

const int MAXN=1005;
int dp[MAXN];
struct node{
    int left,right;
    bool operator <(node n1){
        if(left==n1.left)return right<n1.right;
        else return left<n1.left;
    }
}arr[MAXN];

int main() {
    int T;
    scanf("%d",&T);
    for(int z=1;z<=T;z++){
        int n,left,right,maxs=-1;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&arr[i].left,&arr[i].right);
        }
        arr[0].left=arr[0].right=-1;
        sort(arr+1,arr+n+1);
        ms(dp,0);
        for(int i=1;i<=n;i++){
            int cnt=0;
            for(int j=i;j>=1;j--){
                if(arr[j].right>=arr[i].left)cnt++;
                if(arr[j-1].left!=arr[j].left&&cnt>2)dp[i]=max(dp[i],dp[j-1]+cnt);
            }
            maxs=max(maxs,dp[i]);
        }
        printf("Case #%d: %d\n",z,maxs);
    }
	return 0;
}