[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

1 3 6

4 7 9

8 10 3

1 3 5

4 7 10

8 10 1

1 3 2

4 8 2

9 9 6

10 10 3

【输出样例】

【样例说明】

在[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 longint，l[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
类型	手工	随机	特殊	随机	随机	特殊	随机	随机	随机	随机

program hh;
var f:array[0..500010] of longint;
    first:array[1..500000] of longint;
    e:array[1..250000] of record x,y,next,v:longint; end;
    i,j,k,n,t,s,x,y,v:Longint;
function max(x,y:Longint):Longint;
begin
 if x>y then exit(x) else exit(y);
end;

begin
 assign(input,'net.in');
 reset(input);
 assign(output,'net.out');
 rewrite(output);
 readln(n,t);
 s:=0;
 for i:=1 to n do
  begin
   readln;
   readln(k);
   for j:=1 to k do
    begin
     inc(s);
     readln(x,y,v);
     e[s].x:=x;e[s].y:=y;e[s].v:=v;e[s].next:=first[y];first[y]:=s;
    end;
   end;
 for i:=1 to t do
  begin
   f[i]:=f[i-1]; k:=first[i];
   while k<>0 do
    begin
     f[i]:=max(f[e[k].x-1]+e[k].v,f[i]);
     k:=e[k].next;
    end;
  end;
 writeln(f[t]);
 close(input);close(output);
end.

program hh;

var f:array[0..500010] of longint;

first:array[1..500000] of longint;

e:array[1..250000] of record x,y,next,v:longint; end;

i,j,k,n,t,s,x,y,v:Longint;

function max(x,y:Longint):Longint;

begin

if x>y then exit(x) else exit(y);

end;

begin

assign(input,'net.in');

reset(input);

assign(output,'net.out');

rewrite(output);

readln(n,t);

s:=0;

for i:=1 to n do

begin

readln;

readln(k);

for j:=1 to k do

begin

inc(s);

readln(x,y,v);

e[s].x:=x;e[s].y:=y;e[s].v:=v;e[s].next:=first[y];first[y]:=s;

end;

for i:=1 to t do

begin

f[i]:=f[i-1]; k:=first[i];

while k<>0 do

begin

f[i]:=max(f[e[k].x-1]+e[k].v,f[i]);

k:=e[k].next;

end;

writeln(f[t]);

close(input);close(output);

end.

【个人报告】

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

但确实没想那么多……

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

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

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

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
int n,t,mt,m,px,py,pc;
struct net{
	int x;int y;int c;
};
struct p{
	int y;int c;
};
struct dqueue{
	dqueue(){head=-1;}
	p S[250000];
	int head;
	bool ins(p i){
		if(head==-1){head++;S[head]=i;return 1;}
		if(S[head].c>=i.c)return 0;
		head++;S[head]=i;return 1;
	}
	int get(int i){
		if(head==-1){return 0;}
		int t=head;
		while(t>=0&&S[t].y>i){--t;}
		if(t==-1)return 0;
		return S[t].c;//二分查找我不会= =
	}
};
int cmp(net a,net b){
	return a.y<b.y;
}
vector<net> Q;
dqueue D;
int scanfd(){
	int p=0;
	char c;
	while(c=getchar()){
		if(c-'0'<=9&&c-'0'>=0){break;}
	}
	p=c-'0';
	while(c=getchar()){
		if(c-'0'<=9&&c-'0'>=0){p=p*10+c-'0';}else{break;}
	}
	return p;
}
int main(){
    freopen("net.in","r",stdin);
    freopen("net.out","w",stdout);
	scanf("%d%d",&n,&t);
	while(n--){
		scanf("%d",&m);
		mt+=m;
		while(m--){
			px=scanfd();py=scanfd();pc=scanfd();
			net pn;
			pn.x=px;pn.y=py;pn.c=pc;
			Q.push_back(pn);
		}
	}
	sort(Q.begin(),Q.end(),cmp);
	for(int i=0;i<mt;++i){
		pc=Q[i].c;px=Q[i].x;py=Q[i].y;
		int tmc=D.get(px-1);
		p pyc;
		pyc.c=tmc+pc;pyc.y=py;
		D.ins(pyc);
	}
	cout<<D.get(t)<<endl;
	return 0;
}

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<cmath>

#include<queue>

#include<stack>

using namespace std;

typedef long long ll;

int n,t,mt,m,px,py,pc;

struct net{

int x;int y;int c;

};

struct p{

int y;int c;

};

struct dqueue{

dqueue(){head=-1;}

p S[250000];

int head;

bool ins(p i){

if(head==-1){head++;S[head]=i;return 1;}

if(S[head].c>=i.c)return 0;

head++;S[head]=i;return 1;

}

int get(int i){

if(head==-1){return 0;}

int t=head;

while(t>=0&&S[t].y>i){--t;}

if(t==-1)return 0;

return S[t].c;//二分查找我不会= =

}

};

int cmp(net a,net b){

return a.y<b.y;

}

vector<net> Q;

dqueue D;

int scanfd(){

int p=0;

char c;

while(c=getchar()){

if(c-'0'<=9&&c-'0'>=0){break;}

}

p=c-'0';

while(c=getchar()){

if(c-'0'<=9&&c-'0'>=0){p=p*10+c-'0';}else{break;}

}

return p;

}

int main(){

freopen("net.in","r",stdin);

freopen("net.out","w",stdout);

scanf("%d%d",&n,&t);

while(n--){

scanf("%d",&m);

mt+=m;

while(m--){

px=scanfd();py=scanfd();pc=scanfd();

net pn;

pn.x=px;pn.y=py;pn.c=pc;

Q.push_back(pn);

}

sort(Q.begin(),Q.end(),cmp);

for(int i=0;i<mt;++i){

pc=Q[i].c;px=Q[i].x;py=Q[i].y;

int tmc=D.get(px-1);

p pyc;

pyc.c=tmc+pc;pyc.y=py;

D.ins(pyc);

}

cout<<D.get(t)<<endl;

return 0;

}

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

[Dr.Lib]Note:解题报告 – 上网（DP）

发表评论取消回复

朋友们

TAG CLOUD

发表评论 取消回复

朋友们

TAG CLOUD

发表评论取消回复