|
?
? Problem Description There are n boxes in one line numbered 1 to n, at the beginning, all boxes are black. Two kinds of operations are provided to you:
1 a
i x
i ：You can choose any x
i black boxes in interval [1,a
i], and color them white;
2 a
i x
i ：You can choose any x
i black boxes in interval [a
i,n], and color them white;
lcq wants to know if she use these operations in optimal strategy, the maximum number of white boxes she can get, and if she get maximum white boxes, the minimum number of operations she should use.
Tips:
1. It is obvious that sometimes you can choose not to use some operations.
2. If the interval of one operation didn’t have enough black boxes, you can’t use this operation.
Input The first line contains one integer T, indicating the number of test case.
The first line of each test case contains two integers N (1 <= N <= 1000) and M (1<=M<=1000), indicating that there are N grids and M operations in total. Then M lines followed, each of which contains three integers s
i(1<=s
i<=2) , a
i and x
i (0 <= x
i <= N,1<=a
i<=N), si indicating the type of this operation, a
i and x
iindicating that the interval is [1,a
i] or [a
i,n](depending on s
i), and you can choose x
i black boxes and color them white.
Output For each test case, output case number first. Then output two integers, the first one is the maximum boxes she can get, the second one is the minimum operations she should use.
Sample Input
1
5 2
2 3 3
1 3 3
Sample Output
Case 1: 3 1
/**
hdu 4381 背包变形
题目大意：给定一个区间1~n，所有n个点都是黑色，操作：1 a b 把1~a区间内的b个点变成白色，2 a b 把a~n之间的b个点变成白色，若给定区间黑点数目
不足b个，则该操作不能执行，问最多能变成多少白色，若变成最多的白色那么最少的操作数是多少？
解题思路：我们把1~a操作的区间按a值递增排序，每次先涂最左边的，dp[j]表示用涂满前j个点的最少操作数，状态转移方程为：dp1[j]=min(dp1[j],dp1[j-p1[i].num]+1);
a~n的区间做一个转换后和1~a一样操作。然后枚举涂的个数i即可，dp1[j]+dp2[i-j]<=m,有效。其中i：1~n，j:0~i
*/
#include
#include
#include
#include
using namespace std; struct note { int x,num; bool operator < (const note &other)const { return x
=p1[i].num; j--) { dp1[j]=min(dp1[j],dp1[j-p1[i].num]+1); } } for(int i=0; i
=p2[i].num; j--) { dp2[j]=min(dp2[j],dp2[j-p2[i].num]+1); } } int tmp,ans=0,sum=0; for(int i=1;i<=n;i++) { for(int j=0;j<=i;j++) { tmp=dp1[j]+dp2[i-j]; if(tmp<=m) { if(ans!=i) { ans=i; sum=tmp; } else { sum=min(sum,tmp); } } } } printf(Case %d: %d %d ,++tt,ans,sum); } return 0; }
?
|