[Dr.Lib]Note:解题报告 – 上网(DP)

题4  上网

【问题描述】

假设有n个人要上网,却只有1台电脑可以上网。上网的时间是从1 szw 至 T szw ,szw是sxc,zsx,wl自创的时间单位,至于 szw怎么换算成s,min或h,没有人清楚。依次给出每个人在某个时间段内上网的快乐程度C(必须这个人在整个时间段内都在上网,才能获得快乐程度C,否则,快乐程度是0),请你得到使总的快乐程度达到最大的方案。

【输入格式】

第1行2个整数 n和T,含义如题目所述;

接下来有n个这样的结构(每两个相邻的结构之间有一空行,且第1个结构和第一行间有一空行):

第1行一个整数Mi,表示第i个人的时间段的个数;

接下来有Mi行,每行3个整数Xj,Yj,C,表示第i个人在[Xj,Yj]内上网的快乐程度为C,

因此有Xj-Yj-1=1,X1=1,Ymi=T,Xj<=Yj。

【输出格式】

仅输出一行,为总的最大的快乐程度。

【输入样例】

3 10

 

3

1 3 6

4 7 9

8 10 3

 

3

1 3 5

4 7 10

8 10 1

 

4

1 3 2

4 8 2

9 9 6

10 10 3

【输出样例】

25

【样例说明】

在[1,3]内,安排1上网,快乐程度为6;

在[4,7]内,安排2上网,快乐程度为10;

在[8,8]内,不安排;

在[9,9]内,安排3上网,快乐程度为6;

在[10,10]内,安排3上网,快乐程度为3;

这是使总的快乐程度达到最大的方案,对应的值是25。

【数据范围】

对于30%的数据,n<=4,所有的Mi<=5,T<=20;

对于60%的数据,n<=100,所有的Mi<=100,T<=2000;

对于100%的数据,n<=500,所有的Mi<=500,T<=500000,所有的0<C<=10^9,并保证最终解Max<=10^9。

 

【标程】

很明显,前30%的数据可以用暴力过,直接枚举每一个区间即可,时间复杂度是2^(n*m)

其实,拿到这到题,就很容易想到DP,用max[i]表示第i szw后,所能达到的最大快乐程度,状态转移方程如下:max[i]=max{max[i-1]max[x-1]+C[x,i]},边界情况max[0]=0,其中C[x,i]表示从x时刻开始玩到i时刻的快乐程度。具体操作时,枚举所有结束时刻是i的区间,比较这些区间的初始时刻x对应的max[x-1]+C[x,i]与当前max[i]的大小,如果max[x-1]+C[x,i]更大,就替换max[i]。可能对于很多选手来说,拿出状态转移方程并不难,问题在于怎么存每个区间。如果直接开2维数组,c:array[1..maxT,1..maxT] of longint,空间复杂度是T^2,可以过60%的数据。我们应该如何存区间呢?

我们开一个一维数组,g:array[1..maxn*maxm] of record x,y,c,l:longint; end,空间约4M,其中x,y表示对应区间的初始时刻和结束时刻,c表示快乐程度,l表示上一个和这个区间y值相同的区间所对应的位置。再开一个一维数组,l:array[1..maxT] of longintl[y]表示以y为结束时刻的最后一个区间所对应的位置。这样,我们就可以很轻松的找到以某个值y为结束时刻的区间了。DP的时间复杂度降到 O(maxn*maxm+T)。但事实上由于读入大数据文件比较耗时,所以标程过最后一个数据也要约0.4秒,因此把时限定为1.5s(我们同样可以用x做为标准)

此题主要考察动态规划和链表,拿60分相对容易,拿满分比较困难。

数据范围和类型:

数据 1 2 3 4 5 6 7 8 9 10
N值 3 4 4 65 78 98 400 450 498 500
M值 4 4 5 62 92 98 384 462 498 500
T值 10 16 19 1234 1674 98 25*10^4 35*10^4 45*10^4 5*10^5
平均分 3.81 2.90 3.24 2.33 2.33 2.84 1.19 1.19 1.14 1.08
类型 手工 随机 特殊 随机 随机 特殊 随机 随机 随机 随机

【个人报告】

赛场上前几题耗时太多没来得及打这题。妥妥的DP阿……

但确实没想那么多……

看了题解才知道确实有坑。

抽象的模型大概就是m条带权线段求不相交区间最大权值和……几个几个人是考你读入的……

果断读进来按终点排序,一条一条来DP。

 

 

CC BY-SA 4.0 [Dr.Lib]Note:解题报告 – 上网(DP) by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据