Luogu1622 释放囚犯

发布于 2019-09-21  169 次阅读


这个题是一个区间DP的好题啊(不知道今天为什么要写DP,大概是想跟哈希一样打摆了:joy:)

首先我们暴力考虑,若直接用 f_{i,j} 表示释放第 i 个房间到第 j 个房间的犯人所需要的最小代价,显然 n 太大了,放不下,时间复杂度也显得比较高。

但是我们考虑到 p 比较的小,于是可以将这 p 的需要释放的犯人从小到大排序。

f_{i,j} 表示释放第 i 个到第 j 个需要释放的犯人的最小代价,状态数量就大大减小。

转移:枚举这个区间内第一个释放的犯人 k(i\leq k \leq j) ,此时除开 a_k 之外,a_ia_j 的其他房间都有犯人,所以释放代价是

​ $ (a{j+1}-1)-a{len - 1} - 1$

那么 $f[i][j] = min( f[i][k-1]+f[k+1][j]) + (a{j+1}-1)-a{len - 1} - 1 \ (i\leq k \leq j) $

边界条件 f[i+1][i] = 0

上代码

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1000 + 5;
const int inf = 0x7f7f7f7f;

int P, Q;
int a[SIZE], f[SIZE][SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    P = read(), Q = read();
    for(register int i = 1; i <= Q; i++)
        a[i] = read();
    std::sort(a + 1, a + Q + 1);
    a[Q + 1] = P + 1;
    for(register int len = 1; len <= Q; len++)
        for(register int i = 1; len + i - 1 <= Q; i++)
        {
            int j = i + len - 1;
            f[i][j] = inf;
            for(register int k = i; k <= j; k++)
                f[i][j] = std::min(f[i][j], f[i][k - 1] + f[k + 1][j] + a[j + 1] - a[i - 1] - 2);
        }
    printf("%d", f[1][Q]);
    return 0;   
}

朴实沉毅