乱七八糟的DP题

2017-07-15

831A. Office Keys

time limit per test 2 seconds
memory limit per test 256 megabytes

There are n people and k keys on a straight line. Every person wants to get to the office which is located on the line as well. To do that, he needs to reach some point with a key, take the key and then go to the office. Once a key is taken by somebody, it couldn’t be taken by anybody else.

You are to determine the minimum time needed for all n people to get to the office with keys. Assume that people move a unit distance per 1 second. If two people reach a key at the same time, only one of them can take the key. A person can pass through a point with a key without taking it.

Input

The first line contains three integers n, k and p (1≤n≤1000, n≤k≤2000, 1≤p≤10^9) — the number of people, the number of keys and the office location.
The second line contains n distinct integers a1,a2,…,an (1≤ai≤10^9) — positions in which people are located initially. The positions are given in arbitrary order.
The third line contains k distinct integers b1,b2,…,bk (1≤bj≤10^9) — positions of the keys. The positions are given in arbitrary order.
Note that there can’t be more than one person or more than one key in the same point. A person and a key can be located in the same point.

Output

Print the minimum time (in seconds) needed for all n to reach the office with keys.

Examples

Input1

2 4 50
20 100
60 10 40 80

Output1

Input2

1 2 10
11
15 7

Output2

Note

In the first example the person located at point 20 should take the key located at point 40 and go with it to the office located at point 50. He spends 30 seconds. The person located at point 100 can take the key located at point 80 and go to the office with it. He spends 50 seconds. Thus, after 50 seconds everybody is in office with keys.

题解

DP
题目大意：n个人，k把钥匙，办公室在位置p
读入n个人的位置和k把钥匙的位置
要求每个人拿一把钥匙去办公室，
问最少什么时候所有人都能到办公室。

f[i][j]表示前i个人，在前j把钥匙中都拿到了钥匙，并且到终点的最优最长需求时间。
动态转移方程见代码
注意之前要先排序

#include<bits/stdc++.h>
using namespace std;
long long n,k,p;
long long a[2000];
long long b[2000];
long long f[2000][2000];
//f[i][j]表示前i个人，在前j把钥匙中都拿到了钥匙，并且到终点的最优最长需求时间。
int main()
{
    scanf("%I64d%I64d%I64d",&n,&k,&p);
    for (int i=1;i<=n;i++)
    scanf("%I64d",&a[i]);
    for (int i=1;i<=k;i++)
    scanf("%I64d",&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)//如果i==j，那么第i个人直接匹配第j把钥匙 
            {//求时间最大值 
                f[i][j]=max(f[i-1][j-1],abs(b[j]-p)+abs(a[i]-b[j]));
            } else//否则 不取钥匙j 或者取钥匙j，然后求最小值
            f[i][j]=min(f[i][j-1],max(f[i-1][j-1],abs(b[j]-p)+abs(a[i]-b[j])));
        }
    long long ans=f[n][n];
    for (int i=n;i<=k;i++) ans=min(f[n][i],ans);
    //找一个最小的，i一定要大于n，因为要每个人都有钥匙
    printf("%I64d\n",ans);
    return 0;
}

题目描述

FJ有N (1 <= N <= 20)包干草，干草i的重量是 S_i (1 <= S_i <= 100)，他想尽可能平均地将干草分给3个农场。
他希望分配后的干草重量最大值尽可能地小，比如， B_1,B_2和 B_3是分配后的三个值，假设B_1 >= B_2 >= B_3，则他希望B_1的值尽可能地小。
例如：8包干草的重量分别是：2 4 5 8 9 14 15 20，一种满足要求的分配方案是
农场 1: 2 9 15 B_1 = 26
农场 2: 4 8 14 B_2 = 26
农场 3: 5 20 B_3 = 25
请帮助FJ计算B_1的值。

输入输出格式

输入格式：

Line 1: The number of bales, N.
Lines 2..1+N: Line i+1 contains S_i, the size of the ith bale.

输出格式：

Line 1: Please output the value of B_1 in a fair division of the hay bales.

输入输出样例

输入样例#1：

8
14
2
5
15
8
9
20
4

输出样例#1：

题解

$f[i][j][k]$ 表示使用前i种草料，是否可以使b1为j，b2为k（b3可以通过sum-b1-b2算出来）

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200];
int f[3][2001][2001];// 不用滚动数组就MLE了
int sum;
int main()
{
    scanf("%d",&n);
    f[1][0][0]=1;//初始化，用第1种草料，使b1为0，b2为0，是可以满足的
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];//加进去
        for (int j=0;j<=sum;j++)
            for (int k=0;k<=sum;k++)
            {
                if (f[i%2][j][k])//如果前n-1种草料 可以构成b1=j，b2=k
                {//那么以下三种情况也可以构成
                    f[(i+1)%2][j][k]=1;
                    f[(i+1)%2][j+a[i]][k]=1;
                    f[(i+1)%2][j][k+a[i]]=1;
                }
            }
    }
    int ans=23333333;
    for (int i=1;i<=sum;i++)//求解
        for (int j=1;j<=sum;j++)
        if (f[n%2][i][j]) ans=min(ans,max(i,max(j,sum-i-j)));
    printf("%d\n",ans);
    return 0;
}