cf831D(dp)

题目链接: http://codeforces.com/contest/831/problem/D

 

题意: 有 n 个人和 k 把钥匙, 数组 a 为 n 个人的初始位置, 数组 b 为 k 把钥匙的初始位置, n 个人都要先拿到一把钥匙然后在到 p 位置去, 问所有人都到 p 位置所需要的最少时间是多少.

 

思路: 这题即可以 dp 也可以直接二分答案.

dp 思路为: dp[i][j]存储前i个人在前j把钥匙中每个人得到钥匙的最小花费.

那么动态转移方程式为:

　　if(i == j) dp[i][j] = max(dp[i - 1][j - 1], abs(a[i] - b[j]) + abs(p - b[j]))

　　else if(j > i) dp[i][j] = min(dp[i][j - 1], max(dp[i - 1][j - 1], abs(a[i] - b[j]) + abs(p - b[j])))

 

代码:

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

const int MAXN = 1e3 + 10;
int a[MAXN], b[MAXN << 1], dp[MAXN][MAXN << 1];//dp[i][j]存储前i个人在前j把钥匙中每个人得到钥匙的最小花费

int main(void){
    int n, k, p;
    scanf("%d%d%d", &n, &k, &p);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= k; i++){
        scanf("%d", &b[i]);
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + k + 1);
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= k; j++){
            if(i == j) dp[i][j] = max(dp[i - 1][j - 1], abs(b[j] - a[i]) + abs(p - b[j]));
            else dp[i][j] = min(dp[i][j - 1], max(dp[i - 1][j - 1], abs(b[j] - a[i]) + abs(p - b[j])));
        }
    }
    int sol = 2e9 + 10;
    for(int i = n; i <= k; i++){
        sol = min(sol, dp[n][i]);
    }
    printf("%d\n", sol);
    return 0;
}