HDU

题意：

众所周知lyb根本不学习。但是期末到了，平时不写作业的他现在有很多作业要做。
CUC的老师很严格，每个老师都会给他一个DDL(deadline)。
如果lyb在DDL后交作业，老师就会扣他的分。
现在假设lyb做作业都需要一天。
所以lyb想到要安排做作业的顺序，这样才能尽可能扣少一点分。
请帮帮bx吧。

Input

输入包含T个测试用例。输入的第一行是单个整数T，为测试用例的数量。
每个测试用例以一个正整数N开头(1<=N<=1000)，表示作业的数量。
然后两行。第一行包含N个整数，表示DDL，下一行包含N个整数，表示扣的分。

Output

对于每个测试用例，您应该输出最小的总降低分数，每个测试用例一行。

Sample Input

3
3
3 3 3
10 5 1
3
1 3 1
6 2 3
7
1 4 6 4 2 4 3
3 2 1 7 6 5 4

Sample Output

0
3
5

Hint

上方有三组样例。
对于第一组样例，有三个作业它们的截止日期均为第三天，每天做一个正好在截止日期前全部做完，所以没有扣分，输出0。
对于第二组样例，有三个作业，它们的截止日期分别为第一天，第三天、第一天。第一天做了第一个作业，第二天做了第二个作业，共扣了3分，输出3。

题解：

首先处理一下题目给出的m个区间，如果它们的左端点一样，那么就保留那个右端点最大的那个区间（舍弃的区间都是不用都无所谓的）

然后就可以开始dp了

dp[i][j]表示在  1到i邮票区间  中选出来  j个题目给出的区间  得到的最大不同邮票个数

ri[i]表示，题目给出区间从i开始，最远到达ri[i]结束（就是比如题目给出两个区间[3,5],[3,7]那么ri数组里面就会有ri[3]=7）

那么就会有关系dp[ri[i]][j]=max(dp[i-1][j-1]+ri[i]-i+1,dp[ri[i]][j]);   //对于处理后的ri数组，对于每一个区间[i,ri[i]]只有用和不用两种情况

那么用的时候就是dp[i-1][j-1]+ri[i]-i+1，不用的话就是dp[ri[i]][j]

具体见代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1010;
const int mod=1000000009;
typedef long long ll;
int dp[2020][2020];
int ri[2020];
int main()
{
    ios::sync_with_stdio(false);
    int t,cas=1;
    cin>>t;
    while(t--)
    {
        int n,m,k,i,j;
        mem(dp,0);
        mem(ri,0);
        cin>>n>>m>>k;
        while(m--)
        {
            int l,r;
            cin>>l>>r;
            while(l<=r)
            {
                ri[l]=max(ri[l],r);
                l++;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=k;j++)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
                dp[ri[i]][j]=max(dp[i-1][j-1]+ri[i]-i+1,dp[ri[i]][j]);
            }
        }
        int res=0;
        for(i=1;i<=n;i++)
        {
            res=max(dp[i][k],res);
        }
        cout<<"Case #"<<cas++<<": "<<res<<endl;
    }
    return 0;
}