首页 > 代码库 > Uva 12018 Juice Extractor dp
Uva 12018 Juice Extractor dp
题目链接:点击打开链接
题意:
切水果游戏
给出n个水果
水果出现在屏幕上的时间的区间
1、每次切会把屏幕上所有水果切完
2、当同时切3个或以上时计分,分数为切的水果个数
3、不能遗漏水果
问最高得分
dp[i] 表示 最后一次切第i个的得分。
#include<stdio.h> #include<algorithm> #include<string.h> #include<iostream> using namespace std; #define N 1005 struct node{ int l,r; bool operator<(const node&a)const{ if(a.l==l)return a.r>r; return a.l>l; } }a[1005]; int n; int dp[N]; int main(){ int T, Cas= 1;scanf("%d",&T); a[0].l = a[0].r = -1; while(T--){ scanf("%d",&n); for(int i = 1; i <= n; i++) scanf("%d %d",&a[i].l,&a[i].r); sort(a+1,a+n+1); memset(dp, 0, sizeof dp); for(int i = 3; i <= n; i++){ int sum = 0; for(int j = i; j >= 1; j--){ if(a[j].r>=a[i].l)sum++; if(a[j-1].l != a[j].l) dp[i] = max(dp[j-1] + (sum>2?sum:0),dp[i]); } } int ans = 0; for(int i =1; i <=n;i++)ans = max(ans, dp[i]); printf("Case #%d: %d\n",Cas++,ans); } return 0; } /* 99 4 1 2 2 10 3 4 4 5 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。