自动搬运

查看原文

来自洛谷，原作者为

	君のNOIP。 清新出题人

搬运于2025-08-24 22:20:45，当前版本为作者最后更新于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];
}

---

总结：思路较为简单，细节较多，可以瞎搞骗分。