浙江财经大学
信息管理与工程学院

HDU 4381 Grid

本文由 Ocrosoft 于 2016-08-10 22:09:09 发表

Grid

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 879    Accepted Submission(s): 281

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 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.
 

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

Author
WHU
 

Solution

题意:给定n个块,编号从1到n,以及m个操作,n个块都是黑色的,操作有2种形式,1 ai xi : 从[1,ai]选xi个块将这些块涂白,2 ai xi:从[ai,n]选xi个块将这些块涂白,当区间内黑块的数目不够时则不执行,问最少执行几次,使得最后满足白块最多。

思路:两个01背包,分别记录从前往后涂、从后往前涂的最少执行次数,最后对两个dp数组进行处理,记录答案。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
#define INF 999999 //这里不能是INT_MAX,两个一加会爆int
#define MAXN 1000+10
using namespace std;
int n,m;
struct Node
{
    int a,b;
    bool operator <(const Node t)const
    {return a<t.a;}
};
int main()
{
    int N,cas=1;
    cin>>N;
    while(N--)
    {
        cin>>n>>m;
        int dp1[MAXN],dp2[MAXN];
        for(int i=1; i<=n; i++)dp1[i]=dp2[i]=INF;
        dp1[0]=dp2[0]=0;
        vector<Node> v[3];
        for(int i=0; i<m; i++)
        {
            int x,y,z;
            cin>>x>>y>>z;
            if(x==2)y=n-y+1;
            v[x].push_back((Node){y,z});//学到了...
        }
        sort(v[1].begin(),v[1].end());
        sort(v[2].begin(),v[2].end());
        int vs1=v[1].size(),vs2=v[2].size();
        for(int i=0; i<vs1; i++)
            for(int j=v[1][i].a; j>=v[1][i].b; j--)
                dp1[j]=min(dp1[j],dp1[j-v[1][i].b]+1);
        for(int i=0; i<vs2; i++)
            for(int j=v[2][i].a; j>=v[2][i].b; j--)
                dp2[j]=min(dp2[j],dp2[j-v[2][i].b]+1);
        int ans=0,tmp=0;
        for(int i=0; i<=n; i++)
            for(int j=0; j<=i; j++)
                if(dp1[j]+dp2[i-j]<=m)
                    if(ans!=i)ans=i,tmp=dp1[j]+dp2[i-j];
                    else tmp=min(tmp,dp1[j]+dp2[i-j]);
        printf("Case %d: %d %d\n",cas++,ans,tmp);
    }
    return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 4381 Grid

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址