Codeforces Round #424 (Div. 2) D. Office Keys(dp)

题目链接:Codeforces Round #424 (Div. 2) D. Office Keys

题意:

在一条轴上有n个人,和m个钥匙,门在s位置。

现在每个人走单位距离需要单位时间。

每个钥匙只能被一个人拿。

求全部的人拿到钥匙并且走到门的最短时间。

题解:

显然没有交叉的情况,因为如果交叉的话可能不是最优解。

然后考虑dp[i][j]表示第i个人拿了第j把钥匙,然后 dp[i][j]=max(val(i,j),min(dp[i-1][i-1~j]))   val(i,j)表示第i个人拿第j把钥匙再到门的时间。

然后 后面那个min可以在for的时候保存下来,然后复杂度就O(n*m)了。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4
 5 const int N=2007;
 6 int dp[N/2][N],mi,n,m,s,a[N],b[N];
 7
 8 int val(int i,int j){return abs(a[i]-b[j])+abs(b[j]-s);}
 9
10 int main(){
11     scanf("%d%d%d",&n,&m,&s);
12     F(i,1,n)scanf("%d",a+i);
13     F(i,1,m)scanf("%d",b+i);
14     sort(a+1,a+1+n),sort(b+1,b+1+m);
15     F(i,1,n)
16     {
17         mi=dp[i-1][i-1];
18         F(j,i,m)
19         {
20             dp[i][j]=max(val(i,j),mi);
21             mi=min(mi,dp[i-1][j]);
22         }
23     }
24     int ans=INT_MAX;
25     F(i,n,m)ans=min(ans,dp[n][i]);
26     printf("%d\n",ans);
27     return 0;
28 }

时间: 07-14

Codeforces Round #424 (Div. 2) D. Office Keys(dp)的相关文章

Codeforces Round #424 (Div. 2) D 思维 E set应用,树状数组

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) D. Office Keys 题意:一条直线上,有个办公室坐标 p,有 n个人在a[i],有 k把钥匙在b[i],每个人必须拿到一把钥匙,然后到办公室.问怎么安排花的时间最短. tags:还是不懂套路啊..其实多画两下图就能够感觉出来,2333 关键是要看出来,n个人拿的 n把钥匙应该是连续的. 然后,就是瞎暴力.. #include<bits/stdc++.h> usi

Codeforces Round #424 (Div. 2) C. Jury Marks(乱搞)

题目链接:Codeforces Round #424 (Div. 2) C. Jury Marks 题意: 给你一个有n个数序列,现在让你确定一个x,使得x通过挨着加这个序列的每一个数能出现所有给出的k个数. 问合法的x有多少个.题目保证这k个数完全不同. 题解: 显然,要将这n个数求一下前缀和,并且排一下序,这样,能出现的数就可以表示为x+a,x+b,x+c了. 这里 x+a,x+b,x+c是递增的.这里我把这个序列叫做A序列 然后对于给出的k个数,我们也排一下序,这里我把它叫做B序列,如果我

Codeforces Round #424 (Div. 2) E. Cards Sorting(线段树)

题目链接:Codeforces Round #424 (Div. 2) E. Cards Sorting 题意: 将n个数放进一个队列,每次检查队首,看看是不是队列中最小的数,如果是就扔掉,如果不是就放到队尾. 这样直到队列为空,为需要操作多少次. 题解: 考虑用两个指针模拟,最开始now指针指向第一个数,然后nxt指针指向下一个将要被删除的数. 然后我们要算出这里需要移动多少步,然后删掉这个数,一直重复操作,直到将全部的数删完. nxt指针可以用set来维护,now指针可以用并查集来维护. 计

Codeforces Round #260 (Div. 1) A. Boredom (DP)

题目链接:http://codeforces.com/problemset/problem/455/A A. Boredom time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Alex doesn't like boredom. That's why whenever he gets bored, he comes up with

Codeforces Round #369 (Div. 2) C. Coloring Trees(dp)

题目链接:Codeforces Round #369 (Div. 2) C. Coloring Trees 题意: 有n个树,每个树有一个颜色,如果颜色值为0,表示没有颜色,一共有m个颜色,第j种颜色涂第i棵树需要花费pij,颜色一样且相邻的分为一组 现在要将所有颜色为0的树涂上颜色,使得这些树恰好可以分为k组,问最小的花费 题解: 考虑dp[i][j][k],表示考虑第i棵树涂第j种颜色,当前分为k组的最小花费,然后状态转移看代码,注意的是dp的初始状态 1 #include<bits/std

Codeforces Round #455 (Div. 2) C. Python Indentation dp递推

Codeforces Round #455 (Div. 2) C. Python Indentation 题意:python 里面,给出 n 个 for 循环或陈述语句,'f' 里面必须要有语句.按 python 缩进的方式组合成合法的程序,问有多少种可能方案. tags: dp dp[i][j] 表示第 i 个语句缩进为 j 时的可能方案数, 转移: 1] 如果第 i 个是 'f' , 则第 i+1 个肯定要比第 i 个多缩进一个单位,即 dp[i+1][j] = dp[i][j]. 2]如果

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)

D题fst了,生无可恋.第二场rated的CF,打得精神恍惚 A. Unimodal Array 题意:判断数列是否是单峰的. 像题意那样分为三个阶段随便判一判就好了 #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; int n,x[105],part=1; bool f=1; int main() { scanf(&quo

【推导】Codeforces Round #424 (Div. 1, rated, based on VK Cup Finals) A. Office Keys

选择的钥匙一定是连续的,人和钥匙一定从左到右连续对应. 就枚举钥匙区间即可. #include<cstdio> #include<algorithm> using namespace std; int Abs(int x){ return x<0 ? (-x) : x; } int n,K,p,a[1010],ans=2147483647,b[2010]; int main(){ scanf("%d%d%d",&n,&K,&p);

A. Office Keys (from Codeforces Round #424 (Div. 1, rated, based on VK Cup Finals) )

1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 using namespace std; 6 7 int a[150000]; 8 int b[150000]; 9 int dp[1005][1005]; 10 //dp[i][j] 前i个人从前j个药匙中到达终点的最小时间 11 12 int main() 13 { 14 in