"陶陶" 摘苹果 (动态规划)

$陶陶摘苹果$陶陶摘苹果

$Description$Description

$Solution$Solution

问题转化: $数轴上有若干点,从N个固定区间中选出K个,要求覆盖点数最多.$数轴上有若干点,从N个固定区间中选出K个,要求覆盖点数最多.

• 每个苹果的高度 减去 身高, 进行前缀和处理记为 $sum\left[\right]$sum[]
• $区间去重$区间去重, 保证没有任何一个区间覆盖另一个

然后 排序 进行 $dp$dp,

$F[i,j]$F[i,j] 表示第 $i$i 个区间作为选出的 $j$j 个区间中的最后一个时, 覆盖的最大点数.

则 $F[i,j]=max\left\{F\right[k,j-1]+sum[R_i]-sum[max(R_k,L_i-1)\left]\right\}$F[i,j]=max{ F[k,j−1]+sum[Ri​]−sum[max(Rk​,Li​−1)] } .
时间复杂度 $O\left(m^3\right)$O(m3) .

注意状态的 初始化 和 继承, 继承 不要在 决策 途中进行.

$Code$Code

#include<bits/stdc++.h>
#define reg register

const int maxn = 1000005;
const int maxn_2 = 205;

//{{{
int N;
int M;
int H;
int K;
int cnt;
int Ans;
int flag;
int sum[maxn];
int F[maxn_2][maxn_2];
//}}}

struct Inte{ int L, R; } P[maxn], T[maxn];
bool cmp(Inte a, Inte b){ return a.L==b.L?a.R>b.R:a.L<b.L; }

int main(){
        freopen("apple.in", "r", stdin);
        freopen("apple.out", "w", stdout);
        scanf("%d%d%d%d", &N, &M, &H, &K);
        for(reg int i = 1; i <= N; i ++){
                int x;
                scanf("%d", &x);
                if(x-H > 0) sum[x-H] ++;
                if(x == H) flag ++;
        }
        for(reg int i = 1; i <= M; i ++) scanf("%d%d", &P[i].L, &P[i].R);
        for(reg int i = 1; i < maxn; i ++) sum[i] += sum[i-1];
        std::sort(P+1, P+M+1, cmp);
        for(reg int i = 1; i <= M; i ++){
                int t = i;
                while(i+1 <= M && P[t].L <= P[i+1].L && P[t].R >= P[i+1].R) i ++;
                T[++ cnt] = P[t];
        } 
        K = std::min(K, cnt);
        for(reg int j = 1; j <= K; j ++)
                for(reg int i = 1; i <= cnt; i ++)
                        for(reg int k = 0; k < i; k ++)
                                F[i][j] = std::max(F[i][j], F[k][j-1] + sum[T[i].R] - sum[std::max(T[k].R, T[i].L-1)]);
        for(reg int i = 1; i <= cnt; i ++) Ans = std::max(Ans, F[i][K]);
        printf("%d\n", Ans + flag);
        return 0;
}