Algoogle

Algorithm for Programming Contest

PKU 2430 Lazy Cows

Category: PKU Tag: compress, dp

Lazy Cows

問題概要


2*B(<=15,000,000)のセルにN(<=1,000)頭の牛がいる. この牛全てをカバーするようにK(<=N)個の四角形を作る.
そのときの四角形の面積の総和の最小はいくらか.

解法


DPします.
1段目と2段目に牛がいるのをbitで表現すると配列1本で考えられるので楽です.
また, 牛の数がセルの横幅に対して小さいので位置を座圧します.

各列について, その列を四角形が覆うパターンは5通り.
poj2430-01
この内一つも覆われていないパターンの列は座圧で牛がいる列を詰めるので存在しない.
またこの事から左からセルをなめていくと, 各列は前の列の状態だけから更新されるようなDPを考えられる.
dp[i][k][u] := i列目でk個四角形が存在して状態がuであるものの最小の面積
状態というのは列の覆い方.

あとは場合分けを適当にする.
前の状態から四角形を何個現在の状態につなげるのかを考えれば楽.

コード


(2430.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <cstring>
#include <iostream>

using namespace std;
typedef pair<int,int> pii;
int N, K, B, W;
pii cows[1024];
int unzip[1024];
int cow[1024];
int dp[1024][1024][4];
inline void mymin(int &a, int b){
    if(a < 0) a = b;
    a = min(a, b);
}

int main(){
    scanf("%d%d%d",&N,&K,&B);
    vector<int> tmp;
    for(int i = 0; i < N; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        a--;
        cows[i] = pii(b,a);
        tmp.push_back(b);
    }
    sort(tmp.begin(), tmp.end());
    sort(cows, cows+N);
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    W = tmp.size();
    int cur = 0;
    for(int i = 0; i < W; i++){
        unzip[i+1] = tmp[i];
        while(cur < N and tmp[i] == cows[cur].first){
            cow[i+1] |= (1<<cows[cur++].second);
        }
    }
    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 0;
    for(int i = 0; i < W; i++)
        for(int k = 0; k <= K; k++){
            if(k == 0 and i > 0) continue;
            for(int u = 0; u < 4; u++){
                if(dp[i][k][u] < 0) continue;
                for(int v = 0; v < 4; v++){
                    int cover = v==0? 3: v;
                    int f = __builtin_popcount(cover);
                    if((cover&cow[i+1]) != cow[i+1]) continue;
                    if(k > 0){ // can continue
                        if(v == u or ((v == 1 or v == 2) and u == 3))
                            mymin(dp[i+1][k][v], dp[i][k][u]+f*(unzip[i+1]-unzip[i]));
                        if(v == 3 and k < K and u > 0)
                            mymin(dp[i+1][k+1][v], dp[i][k][u]+unzip[i+1]-unzip[i]+1);
                    }
                    if(k < K and v < 3) mymin(dp[i+1][k+1][v], dp[i][k][u]+f);
                    if(v == 3 and k < K-1) mymin(dp[i+1][k+2][v], dp[i][k][u]+f);
                }
            }
        }

    int ans = 2*B;
    for(int i = 0; i < 4; i++)
        if(dp[W][K][i] >= 0) mymin(ans, dp[W][K][i]);
    printf("%d\n", ans);
    return 0;
}

Comments