P8286 「DAOI R1」Ciky

櫻尘ིོི༹ · 2022-03-02 23:19:07 · 题解

出题人题解

Subtask 0

暴力枚举每片叶子用哪个画笔画，画哪些叶子能使美观值最大。

裸搜。

时间复杂度 O(n^m)

Subtask 1

考虑 dp 。

将画笔按长度从小到大排序，将叶子按美观程度从小到大排序。

每次选出一片叶子后，看用至少用哪支画笔可以画，则它后面的每一支画笔都可以画。

for(int i=1;i<=m;++i){
    int v,s;
    int p=lower_bound(c,c+n,s)-c;
    for(int j=n;j>=p+1;--j)dp[j]=max(dp[j],dp[j-1]+1);
}

计算美观值最大同理。

for(int i=1;i<=m;++i){
    int v,s;
    int p=lower_bound(c,c+n,s)-c;
    for(int j=n;j>=p+1;--j)dp[j]=max(dp[j],dp[j-1]+v);
}

时间复杂度 O(nm)

Subtask 2

正解贪心。

将画笔按长度从大到小排序，将叶子按美观度从小到大排序。

由于与越长的画笔匹配的叶子理应美观度越大，且边长小的叶子也能与长的画笔匹配。所以让长度长的画笔匹配满足条件下最大美观度的叶子一定不亏，反复执行这样不亏的操作，最后得到的即是最优解。

适用于维护最长以及美观度最大，但维护美观度最大需要用优先队列维护。

priority_queue<int> q;
int head=1;
for(int i=1;i<=m;++i){
    for(int j=head;j<=n;++j){
        if(a[j].s>c[i]||blog){
            head=j;
            break;
        }
        q.push(a[j].v);
        if(j==n)blog=true;
    }
    if(!q.empty())sum+=q.top(),q.pop();
}

时间复杂度 O(n \log n)