Peienwu's Blog

Hello world

0%

[題解]APCS美食博覽會

發表於 分類於 Valine：
文章字數： 1.8k 所需閱讀時間 ≈ 2 分鐘

P4 美食博覽會

題目連結

對於序列中k個連續的區間，每一個區間滿足區間內的元素皆不重複，區間範圍可以重疊（不過重疊部分只會算一次），找出這k個連續區間所能覆蓋到的最大長度。

感覺跟背包問題的概念有點像，n個物品可以對應到k個區間，重量則對應到這裡的序列中的數字。這題用DP解。

定義

定義 $dp[i][j]$ 為 $i$ 個試吃員，看了前 $j$ 個攤位，最多可以吃到幾個攤位。

轉移式

維護一個函數 $f[i]$ 表示如果試吃員吃了第 $i$ 個攤位的美食，他所能吃到最左端的攤位的索引值。也就是說，試吃員可以吃 $f[i]$ 到 $i$ 攤位的美食。

轉移式代表了要使用第 $i$ 的攤位作為右端點，或是不要使用（直接用前一個），取兩者的最大值。後面一串加減是計算區間大小

邊界

從轉移式可以看到他空間可以用滾動DP優化！

GREEDY的作法？
如果每一次都選擇最大的區間，並將這個區間的值都改成0，做7次，得到答案，是正確的做法嗎？

最大的區間不一定會被完全選到。以下測資：

12 2
5 4 3 2 1 3 4 5 6 4 3 2

如果是Greedy會選擇 $2 \,1\, 3\, 4\, 5\, 6$ ，然後從兩邊挑一邊。答案是 $9$。
但是用DP做會是 $5\, 4\, 3\, 2\, 1$ 加上 $5\, 6\, 4\, 3\, 2$，答案是 $10$。

時間複雜度： 兩層迴圈總共是 $O(kn)$

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
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define int long long
#define N 1000005
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define INF 2e18
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,k,dp[2][N],lft[N],arr[N];
int mp[N];

signed main(){
    Orz;
    cin>>n>>k;
    memset(dp,0,sizeof(dp));
    memset(lft,0,sizeof(lft));
    memset(mp,0,sizeof(mp));
    rep(i,1,n)cin>>arr[i];
    int maxn = 0;
    for(int i=1;i<=n;i++){
        if(mp[arr[i]]!=0){
            lft[i] = mp[arr[i]]+1;
            mp[arr[i]] = i;
        }
        else{
            lft[i] = 1;
            mp[arr[i]] = i;
        }
        lft[i] = max(maxn,lft[i]);
        maxn = max(maxn,lft[i]);
    }

    
    for(int i=0;i<k;i++){
        for(int j=1;j<=n;j++){
            dp[1][j] = max(dp[1][j-1],dp[0][lft[j]-1]+j-lft[j]+1);
        }
        for(int j=1;j<=n;j++){
            dp[0][j] = dp[1][j];
        }
    }
    cout<<dp[1][n]<<endl;
}

// 1 1 2 1 4 1 7 1 3 8
// 1 1 2 2 4 4 7 7 7 8

EXTRA 版本

BY thanksone

熟悉的題目，大的感人的k。如果依照上面$O(nk)$的做法肯定TLE。
俗話說得好 : “好的DP定義是AC的一半”
因此經過一系列通靈，我們得到了一個非常漂亮的定義

定義

$dp[i] =$ 必須選第 $i$ 家，$($能吃最多的攤販數量，需要的人數$) (dp[i]$是一個$pair)$

轉移式

維護一個函數 $L[i]$ ，其實就是樓上的 $f[i]$，但是我比較想要叫他 $L$

$max(a, b) = a, if(a.first > b.first\ or\ (a.first == b.first\ and\ a.second > b.second))$

優化

Aliens優化 : 利用penalty限制人數
每當有一個人加入，便扣除 $p$ 個攤販的業績
當總人數超過 $k$，表示 $p$ 不夠大，仍然有太多人利大於弊
反之，當總人數小於 $k$，表示 $p$ 太大，有太多人弊大於利
看出來了嗎? $p$ 可以二分搜喔!

時間複雜度： 二分搜加每次DP $O(nlogn)$

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
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
int n, k;
array<int, 100004> A/*num of stands*/, L/*leftest stand can eat to*/, cnt/*count of each num*/;
array<pii, 100004> dp;
pii add(pii p, int v){
    p.ff += v;
    p.ss++;
    return p;
}
pii max(pii a, pii b){
    if(a.ff == b.ff) return a.ss > b.ss? a : b;
    return a.ff > b.ff ? a : b;
}
pii DP(int p){
    //ff = stands visited, ss = people needed
    pii ans = {0, 0};
    int l = 0;
    for(int i = 0; i < n; i++){
        while(l < L[i]) ans = max(ans, dp[l++]);
        dp[i] = add(ans, i - L[i] + 1 + p);
    }
    while(l < n) ans = max(ans, dp[l++]);
    return ans;
}
int BIS(){
    int l = -n, r = n, mid;
    while(l != r){
        //binary search penalty
        mid = (l + r) >> 1;
        if(DP(mid).ss < k) l = mid + 1;
        else r = mid;
    }
    return DP(l).ff - l * k;
}
signed main(){
    cin >> n >> k;
    int l = 0;
    for(int i = 0; i < n; i++){
        cin >> A[i];
        cnt[A[i]]++;
        while(cnt[A[i]] > 1) cnt[A[l++]]--;
        L[i] = l;
    }
    cout << BIS();
    return 0;
}