题面
传送门 大意: 把一个序列分成k份,使得每一份前m大的值的和最大。
解答
比赛时读错题了,以为是单调队列优化DP,唉,菜是原罪。贪心,把数组排个序取前m×k各数就行了 至于划分方案,贪心,取够m个最大就不取了。 代码:
//
// Created by dhy on 19-2-10.
//
# include <cstring>
# include <vector>
# include <cstdio>
# include <cmath>
# include <deque>
# include <algorithm>
using namespace std;
int read(){
int x = 0,f = 1;
static char c = getchar();
while(c<'0'||c>'9'){ if(c=='-')f = -1;c = getchar(); }
while(c>='0'&&c<='9'){ x = (x<<1)+(x<<3)+c-'0';c = getchar(); }
return x*f;
}
const int MAXN = (int)2e5+10;
int a[MAXN];pair<int,int>b[MAXN];
bool match[MAXN];
int as[MAXN];int cnt;
int main(){
int n = read(),m = read(),k = read();
for(int i = 1;i<=n;i++)a[i] = read(),b[i].first = a[i],b[i].second = i;
sort(b+1,b+1+n);
long long ans = 0;
vector<int> ind(m*k);
for(int i = n;i>=n-m*k+1;i--){
match[b[i].second] = true;
ans+=b[i].first;
}
printf("%lld\n",ans);
int curr = 0;
for(int i = 1;i<=n;i++){
if(match[i])curr++;
if(curr>=m)as[++cnt] = i,curr=0;
}
for(int i = 1;i<k;i++)printf("%d ",as[i]);
return 0;
}