Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

售票厅出售关于音乐会的票，取代原来的卖一张票的形式，而是一组座号连续的票。售票室已经收到很多预订。每个预订包含指定

最小座号的一组连续的票。

售票厅不能满足所有这样的订票。如果出售所有这样的订票，那么将会有大量数目的座号为空。于是售票室作了如下的安排和价

格策略，如果一个订单被接受并且安排了确定的作为，则预定者必须付全部的票的价格(2元)。如果一个订票被接受，但是被安

排的位置与申请的位置不一样（最少有一个位置），那么预定者只需付一半的价格（1元）。

售票室的目标是最大限度增加售票总收入。

【编程任务】

你的任务是编写一个程序，计算出售票厅最大能能获得的收入，并输出对应他们选择的预订中座位的安排方案。

【输入格式】

第一行包含两个整数M 和L。M(1 ≤M≤ 30 000)表示座位的数量，L(1 ≤L≤ 100)表示每组预订中连续座位的数目。座位纺编号从1到M。第二行包含一个整数N，N(1≤N≤100 000)表示预订的数量，第三行包含N个整数，表示预订，其中该行的第i个整数 z(1 ≤z≤ M-L+1)，表示第i个预订要求从座位号Z开始，到座位号z+L-1结束。

【输出格式】

输出的第一行包含一个整数S，表示最大的收入，第二行包含一个整数Q，表示被接受的预订数。

【数据规模】

Sample Input1

20 3

7

4 2 10 9 16 15 17

Sample Output1

9

6

【样例说明】

Q行描述座位的分配，每行包含一对整数x y，表示买者x购买从编号y开始的一组票。输出时座位号必须严格递增，可能有多种输出方案。

4 1

1 4

2 7

3 10

6 13

5 16

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u253

【题解】



设f[i]表示前i个座位能获得的最大利润；

设g[i]表示前i个座位安排了几个人的预定(有可能是随便找个预定放在前面以赚取1元钱);

设h[i]表示前i个座位有多少个预定是随便找一个人预定的(即不是符合它要求的);

再设一个bo[i]表示是否有一个人的预定的连续的座位的最后一个座位在i号座位；

我用程序讲

rep1(i,l,m)//枚举座位

    {

        if (g[i-l] <n)//如果i-l的位置安排的预定数小于n

        {

            if (bo[i])//如果有一个预定的连续的座位的最后一个位置在i号

            {

                f[i] = f[i-l]+2;//则可以安排这个人的需求;

                g[i] = g[i-l]+1;//安排的预定数递增

                temp[i] = temp[i-l];//这个过程没有增加不符合要求的人

            }

            else//如果没有人的预定结尾在这里

            {

                if (f[i]<f[i-l]+1)//就随便找一个人的预定放在这里；

                {//如果更优就更新

                    f[i] = f[i-l]+1;

                    g[i] = g[i-l]+1;

                    temp[i] = temp[i-l]+1;//递增随便预定的人的个数

                }

            }

        }

        if (bo[i] && g[i-l]==n && temp[i-l]>0)

        {//如果有一个人的预定结尾在这里,但是之前的预定已经到达n了,但是前面的座位有一些是随便给的(当前以i结尾的预定肯定也在之前随便给了);

//那么就把那个之前随便给的预定放在这个地方来,这样总的收益就会增1(之前算作没有按照要求的安排已经增加了1);

            f[i] = f[i-l]+1;

            g[i] = n;//安排的预定数还是不变->这个g数组是用来限制那些随便安排的预定个数的;

            temp[i] = temp[i-l]-1;//随便安排的预定个数递减.

        }

        rep1(j,i-l,i-1)//如果不这样循环的话会和程序的预定方案不一样。实际上判断一下f[i-1]是不是大于f[i]就可以了。。看程序吧.

            if (f[j]>f[i])

            {

                f[i] = f[j];

                g[i] = g[j];

                temp[i] = temp[j];

            }

【完整代码】

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <set>

#include <map>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <string>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

void rel(LL &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t) && t!='-') t = getchar();

    LL sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

void rei(int &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t)&&t!='-') t = getchar();

    int sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

const int MAXN = 3e4+100;

const int dx[5] = {0,1,-1,0,0};

const int dy[5] = {0,0,0,-1,1};

const double pi = acos(-1.0);

int m,l,f[MAXN],g[MAXN],n,temp[MAXN];

bool bo[MAXN] = {0};

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    rei(m);rei(l);

    rei(n);

    rep1(i,1,n)

    {

        int z;

        rei(z);

        bo[z+l-1] = true;

        f[z+l-1] = 2;

        g[z+l-1] = 1;

        temp[z+l-1] = 0;

    }

    rep1(i,l,m)

    {

        if (g[i-l] <n)

        {

            if (bo[i])

            {

                f[i] = f[i-l]+2;

                g[i] = g[i-l]+1;

                temp[i] = temp[i-l];

            }

            else

            {

                if (f[i]<f[i-l]+1)

                {

                    f[i] = f[i-l]+1;

                    g[i] = g[i-l]+1;

                    temp[i] = temp[i-l]+1;

                }

            }

        }

        if (bo[i] && g[i-l]==n && temp[i-l]>0)

        {

            f[i] = f[i-l]+1;

            g[i] = n;

            temp[i] = temp[i-l]-1;

        }

        rep1(j,i-l,i-1)

            if (f[j]>f[i])

            {

                f[i] = f[j];

                g[i] = g[j];

                temp[i] = temp[j];

            }

        /*if (f[i-1]>f[i]) 这样写也可以，但是得到的方案会和测试点的方案不一样。认为你错了..

        {

            f[i] = f[i-1];

            g[i] = g[i-1];

            temp[i] = temp[i-1];

        }

        */

    }

    cout << f[m]<<endl;

    cout << g[m]<<endl;

    return 0;

}