选元素
给定一个长度为 n 的整数序列 $a_1,a_2,…,a_n$。
请你从中挑选 x 个元素,要求:
- 原序列中的每一个长度为 k 的连续子序列都至少包含一个被选中的元素。
- 满足条件 1 的前提下,所选 x 个元素的相加之和应尽可能大。
输出最大可能和。
输入格式
第一行包含三个整数 n,k,x。
第二行包含 n 个整数 $a_1,a_2,…,a_n$。
输出格式
如果无法满足题目要求,则输出 −1。
否则,输出一个整数,表示所选元素的最大可能和。
数据范围
前三个测试点满足 1≤k,x≤n≤6。
所有测试点满足 1≤k,x≤n≤200,$1≤a_i≤10^9$。
输入样例1:
5 2 3
5 1 3 10 1
输出样例1:
18
输入样例2:
6 1 5
10 30 30 70 10 10
输出样例2:
-1
输入样例3:
4 3 1
1 100 1 1
输出样例3:
100
思路
闫式dp分析法
状态表示f[i][j]:表示在前i个数中选,且包含第i个数,一共j个数的所有集合,属性:max
状态计算:
f[i][j]:当前已经第j个点在第i个位置,那么第j-1个点与第j个点之间的点数个数应该不大于k,那么假设倒数第二个点
即第j-1个点的下标是t 则 i-k<=t<i
那么f[i][j]=max(f[i][j],f[t][j-1]+a[i]) t=>(i-k<=t<i)
最后的结果是在n-k+1 ~ n之间选择一个最后一个点取最大值即可,
代码
#include <bits/stdc++.h>
using namespace std;
const int N=210;
typedef long long LL;
LL f[N][N];
LL a[N];
int n,k,x;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k>>x;
for(int i=1;i<=n;i++) cin>>a[i];
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=x;j++){
for(int t=max(0,i-k);t<i;t++){
f[i][j]=max(f[i][j],f[t][j-1] + a[i]);
}
}
}
LL res = -1;
for(int i=n-k+1;i<=n;i++) res = max(res , f[i][x]);
cout<<res<<endl;
return 0;
}
单调队列优化
#include <bits/stdc++.h>
using namespace std;
const int N=210;
typedef long long LL;
LL f[N][N];
int a[N];
int q[N];
int hh=0,tt=-1;
int n,k,x;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k>>x;
for(int i=1;i<=n;i++){
cin>>a[i];
LL q = a[i];
}
//f[i][j]表示当前已经选择了i个点,且最后一个点的位置是j的所有集合,属性max
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=x;i++){
int hh=0,tt=-1;
for(int j=0;j<=n;j++){
if(hh<=tt && q[hh] + k < j ) hh++;
if(hh<=tt) f[i][j] = f[i-1][q[hh]] + a[j];
while(hh<=tt && f[i-1][q[tt]] <= f[i-1][j]) tt--;
q[++tt] = j;
}
}
LL res = -1;
for(int i=n-k+1;i<=n;i++) res = max(res, f[x][i]);
cout<<res<<endl;
return 0;
}
为什么第二种方法j从0开始
因为在单调队列中,你会发现你需要0这个点去更新后面的点(在第一种方法中,t最小是从0开始的),虽然它没有意义,但是还是需要把它加在队列中
说的对。t从0开始实际运算上是为了从
f[0][0]
帮助转移f[i][1]
的类型,i<=k。如本题第一个样例中,在窗口为2的情况下
f[3][1]=-inf
, 将窗口改为3,则计算f[3][1]
需要f[2][0],f[1][0],f[0][0]
转移,而若t取不到0时f[0][0]
是无法取到的,会导致错误结果。也就是说只有计算f[i][1]
的时候需要f[0][0]
而只有这一步需要t = 0
。故为了让t不从0开始,只需要初始化i <=k
的f[i][1]
即可。不需要初始化f[0][0]
虽然会速度变慢,但是能够加深理解吧。
代码:
第二个方法去0:
请问为什么最里面的循环取的是max(0, i - k),而不能是max(1, i -k),最前面的点不应该是a[1]吗
好像有点懂了,我先初始化dp[1][1]到dp[k][1],再去max(1, i-k)结果就对了。是为了保证求dp[i][j]时,dp[u][j - 1]已经求过了吗?可以这样理解吗
那个是去循环子状态,子状态需要用到0这个点,所以需要枚举他
lihai
%%%和y总思路一样
固定序列和k的话,答案关于 x 是不是上凸的呢(也就是能不能用 wqs 二分继续优化)?
不太理解你意思
https://www.luogu.com.cn/discuss/437118 参见这个讨论帖
wqs 二分可以 O(nlogn)
我又试了试,发现固定序列和 k 的话,答案关于 x 好像是非严格单调递增的?
其实很好理解,选的机会多了,答案一定不会更劣/kk
贪心能做吗
??
没有不选的方案?
要选出最大的,所以能选则选
LL q = a[i]是什么意思呀
我瞎写的 ~v~