2017 ACM-ICPC 亚洲区(乌鲁木齐赛区)网络赛 D.Hack Portals

计蒜客上的题没地方补,但是发现这题是POJ原题(连样例都没改)

题目链接:POJ 1991 : Turning in Homework

题目大意:从原点到$H$ 有$C$ 个教室,每个教室的作业有最早提交时间,问从原点出发将所有作业都提交完后到达$B$ 点所需要的最少时间。

DP+贪心

注意到若有连续的若干个教室$[l,r]$ 均没交作业,那么下一步最优的做法仅可能先到两端($l$ 或$r$ )(若先到中间,则必然会折返回来,而这部分时间花费实际是不必要的)。

故可以定义状态$dp[i][j][0]$ 表示当前在位置$i$ ,$(i,j]$ 间的教室作业都没交的最小花费;$dp[i][j][1]$ 表示当前在位置$i$ ,$[i,j)$ 间的教室作业都没交的最小花费。

复杂度$O(n^2)$ 。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1000+5;
const ll inf=1e15;
ll c,h,b,dp[N][N][2];
struct node{
ll p,t;
friend bool operator<(node a,node b){
return a.p<b.p;
}
}a[N];
ll Abs(ll x){return x>0?x:-x;}
ll Max(ll x,ll y){return x>y?x:y;}
ll Min(ll x,ll y){return x<y?x:y;}
ll solve(ll l,ll r,ll op){
if(l<0||r>=c)return inf;
if(dp[l][r][op]!=-1)return dp[l][r][op];
if(op==0){
dp[l][r][op]=Min(Max(solve(l-1,r,0)+Abs(a[l-1].p-a[l].p),a[l].t),Max(solve(l,r+1,1)+Abs(a[r+1].p-a[l].p),a[l].t));
}else{
dp[l][r][op]=Min(Max(solve(l-1,r,0)+Abs(a[l-1].p-a[r].p),a[r].t),Max(solve(l,r+1,1)+Abs(a[r+1].p-a[r].p),a[r].t));
}
return dp[l][r][op];
}
int main(void){
scanf("%lld%lld%lld",&c,&h,&b);
for(int i=0;i<c;++i)scanf("%lld%lld",&a[i].p,&a[i].t);
sort(a,a+c);
memset(dp,-1,sizeof(dp));
dp[0][c-1][0]=Max(a[0].p,a[0].t);
dp[0][c-1][1]=Max(a[c-1].p,a[c-1].t);
ll ans=inf;
for(int i=0;i<c;++i)
ans=Min(ans,solve(i,i,0)+Abs(a[i].p-b));
printf("%lld\n",ans);
}
# dp, 贪心

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×