题解 P6434 【「EZEC-1」甜品】

君のNOIP。 · 2020-04-19 21:04:56 · 题解

首先是问题一：

20分：O(2^n) 直接爆搜即可。

40分：O(kn^2) 暴力 dp。

首先将美味值排序。

设 dp_{i,j} 为以第 i 种结尾选了 j 种的方案数。

可以发现 dp_{i,j} 为 \sum\limits_{a_p\times l\le a_i}^{a_p\times r\ge a_i} dp_{p,j-1}

这个过程三重 for 循环模拟即可。

答案就是 \sum\limits_{i=k}^n dp_{i,k}

60分：由于 a_i 比较小，这是给开桶的做法过的，这里不详解了。

100分: O(nk + nlogn)

参考40分思路，我们发现瓶颈在于第 3 重循环的寻找符合条件的 p

我们可以设 dp_{i,j} 为到第 i 种选了 j 种的方案数。

首先很显然 dp_{i,j}\gets dp_{i-1,j}

然后我们只需知道对于每个 i 最大的 p 和最小的 p ，满足 a_p\times l\le a_i ，a_p\times r\ge a_i

这个过程我们可以 O(n) 预处理得出。

如下：

int mi[MlX_N],ma[MlX_N];
int li=0,la=0;
for(int i=1;i<=n;i++) {
    while(va[la+1] * l <= va[i] && la < i-1)la++;
    while(va[li+1] * r < va[i] && li < i-1)li++;
    mi[i]=li;
    ma[i]=la;
    dp[i][1]=i; //初始化
}

其中 ma_i 表示最大的 p 使 a_p\times l\le a_i ，而 mi_i 表示最大的 q 使 a_q \times r < a_i （这样保证a_{q+1} \times r \ge a_i）

那么 \sum\limits_{a_p\times l\le a_i}^{a_p\times r\ge a_i} dp_{p,j-1} 就是 dp_{ma_i,j-1} - dp_{mi_i,j-1}

综上转移方程为：

dp[i][j] = (dp[i-1][j] + dp[ma[i]][j-1] - dp[mi[i]][j-1] + mod) % mod;

注意：

由于一开始卡空间，这里给的是滚动数组。
转移前要判断，若 dp_{ma_i,j-1} < dp_{mi_i,j-1} 则加上 mod ，以保证不出现负数，同时也不超 int

对于问题二，有两种方法：

贪心：从最大的往前选，然后每次跳到 ma_{now} ，第一次选满 k 种即为最优解，就输出答案并直接 exit(0)

时间复杂度： O(???)

由于是爆搜，时间复杂度很玄学，在随机数据下会比第二种方法 dp 快。

部分代码：


void dfs(int t,int now,int s){
    if(t==1){
        cout<<s;
        exit(0);
    }
    for(int i=ma[now];i>mi[now];i--)
            dfs(t-1, i, (s + va[i]) % mod );
}

int main(){
    for(int i=n;i>=k;i--)
        if(va[i] != va[i+1])
            dfs(k, i, va[i]);

    cout<<0;
}

还是 dp ，转移方程也仅有一行。

设 f_{i,j} 为到第 i 种选了 j 种的美最大味值之和。

很显然还是 f_{i,j}\gets f_{i-1,j}

然后可以发现 f_{i,j}\gets f_{ma_i,j-1} + a_i

二者取最大值即可。

但仅当以第 i 种结尾选 k 种的方案存在时，我们才能考虑后者。

所以转移方程为：

f[i][j&1]= max(f[i-1][j&1], (dp[i][j&1] != dp[i-1][j&1] ? f[ma[i]][j&1^1] + va[i] : 0 ) )%mod ;

完整代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define mod 1000000007
#define G() Cr=getchar()
int Xr;char Cr;
inline int rd(){
    Xr=0,G();
    while(Cr<'0'||Cr>'9')G();
    while(Cr>='0'&&Cr<='9')Xr=(Xr<<3)+(Xr<<1)+Cr-'0',G();
    return Xr;
}
#define MlX_N 2000005
int n,k;
int l,r;
int va[MlX_N];
int li,la;
int mi[MlX_N],ma[MlX_N];
int dp[MlX_N][2];
int f[MlX_N][2];
int main(){ 
    n=rd(),k=rd(),l=rd(),r=rd();
    for(int i=1;i<=n;i++)va[i]=rd();
    sort(va+1, va+1+n);
    for(int i=1;i<=n;i++) {
        while(va[la+1] * l <= va[i] && la < i-1)la++;
        while(va[li+1] * r < va[i] && li < i-1)li++;
        mi[i]=li;
        ma[i]=la;
        dp[i][1]=i;
        f[i][1]=va[i];
    }

    for(int j=2;j<=k;j++) {
        for(int i=1;i<=n;i++) {
            if(dp[ma[i]][j&1^1] < dp[mi[i]][j&1^1])
                dp[i][j&1] = (dp[i-1][j&1] + dp[ma[i]][j&1^1] - dp[mi[i]][j&1^1] + mod ) % mod;
            else
                dp[i][j&1] = (dp[i-1][j&1] + dp[ma[i]][j&1^1] - dp[mi[i]][j&1^1] ) % mod;

            f[i][j&1] = max(f[i-1][j&1], (dp[i][j&1] != dp[i-1][j&1] ? f[ma[i]][j&1^1] + va[i] : 0 ) ) % mod;
        }
    }

    cout<<dp[n][k&1]<<endl<<f[n][k&1];
}