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;
}