首页 > 代码库 > Codeforces Round #424 (Div. 2) D. Office Keys(dp)

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

2024-10-26 07:02:02   209人阅读

题目链接：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 }
View Code

 

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


联系
我们