2015
05-24

# Grid

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 ai xi ：You can choose any xi black boxes in interval [1,ai], and color them white;
2 ai xi ：You can choose any xi black boxes in interval [ai,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.

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 si(1<=si<=2) , ai and xi (0 <= xi <= N,1<=ai<=N), si indicating the type of this operation, ai and xi indicating that the interval is [1,ai] or [ai,n](depending on si), and you can choose xi black boxes and color them white.

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 si(1<=si<=2) , ai and xi (0 <= xi <= N,1<=ai<=N), si indicating the type of this operation, ai and xi indicating that the interval is [1,ai] or [ai,n](depending on si), and you can choose xi black boxes and color them white.

1
5 2
2 3 3
1 3 3

Case 1: 3 1

Brief Description:

1 ai xi : 从[1,ai]选xi个块，将这些块涂白。

2 ai xi：从[ai,n]选xi个块，将这些块涂白。

Analysis:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
const int maxn = 2005;
struct node{
int aa,cor;
node(){}
node(int _aa,int _cor){
aa = _aa;   cor = _cor;
}
}x1[maxn],x2[maxn];
int n,m;
int dp1[maxn],dp2[maxn];
int sumx1,sumx2;

bool cmp(const node &p,const node &q){
return p.aa < q.aa;
}

int main()
{
int cas,ta=1;
scanf("%d",&cas);
while(cas--){
int i,j;
scanf("%d%d",&n,&m);

sumx1 = sumx2 = 1;
for(i=0; i<m; i++){
int key,yy,z;
scanf("%d%d%d",&key,&yy,&z);
if(key == 1){
x1[sumx1++] = node(yy,z);
}else{
x2[sumx2++] = node(n+1-yy,z);
}
}
sort(x1+1,x1+sumx1,cmp);
sort(x2+1,x2+sumx2,cmp);
memset(dp1,0x3f,sizeof(dp1));
memset(dp2,0x3f,sizeof(dp2));

dp1[0] = dp2[0] = 0;
for(i=1; i<sumx1; i++){
for(j=x1[i].aa; j>=x1[i].cor; j--){
dp1[j] = min(dp1[j],dp1[j-x1[i].cor]+1);
}
}// for

for(i=1; i<sumx2; i++){
for(j=x2[i].aa; j>=x2[i].cor; j--){
dp2[j] = min(dp2[j],dp2[j-x2[i].cor]+1);
}
}// for

int ans = 0,anssum = 0,tmp;
for(i=1; i<=n; i++){
if(i == 3){
tmp = 1;
}
for(j=0; j<=i; j++){
tmp = dp1[j] + dp2[i-j];
if(tmp <= m){
if(ans != i){
ans = i;   anssum = tmp;
}else if(tmp < anssum){
anssum = tmp;
}
}
}
}

printf("Case %d: %d %d\n",ta++,ans,anssum);
}
return 0;
}