题解 CF1394A 【Boboniu Chats with Du】
绝顶我为峰
2020-08-13 20:15:02
看完题目感觉是 $dp$ 题目，考虑做法。
发现从前往后推不好做，我们考虑倒着做。
首先将 $a$ 按照和 $m$ 的大小关系分成两组，每组从小到大排序。显然 $dp_n=\max\{a_i\}$，然后考虑每一天，有不禁言和禁言两种选择。
- 如果不禁言，首先 $a_i\leq m$ 的一堆应不为空，那么从 $a_i\leq m$ 的一堆选择没有被使用过的最大值 $maxa$，然后 $dp_i=dp_{i+1}+maxa$。
- 如果禁言，首先 $i+d+1\leq n$ 且 $a_i>m$ 的一堆不为空，那么从 $a_i>m$ 的一堆选择没有被使用过的最大值 $maxa'$，然后 $dp_i=dp_{i+d+1}+maxa'$。
如果以上两种转移都无法进行，那么 $dp_i=dp_{i+1}$。
我们发现这样需要 $n$ 组堆或其他数据结构维护未使用的 $a$，无法承受。
于是我们改用 $vector$ 或数组存储，将先前的 $dp_i$ 记为 $dp_{i,0}$，并且增加 $dp_{i,1},dp_{i,2}$，分别表示未被使用的最大值的位置，这样我们只需要两个 $vector$ 即可。
最后的答案是 $\max\{dp_{i,0}\}$。
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
int n,m,d,a[100001],dp[100001][3],sum,cnt1,cnt2;
vector<int> q1,q2;
signed main()
{
cnt1=cnt2=-1;
scanf("%lld%lld%lld",&n,&d,&m);
for(register int i=1;i<=n;++i)
{
dp[i][0]=-1;
scanf("%lld",&a[i]);
if(a[i]>m)
{
q1.push_back(a[i]);
++cnt1;
}
else
{
q2.push_back(a[i]);
sum+=a[i];
++cnt2;
}
}
if(q1.empty())
{
printf("%lld\n",sum);
return 0;
}
sort(q1.begin(),q1.end());
sort(q2.begin(),q2.end());
dp[n][0]=q1[cnt1];
dp[n][1]=cnt1-1;
dp[n][2]=cnt2;
for(register int i=n-1;i>=1;--i)
{
if(dp[i+1][2]>=0)
{
dp[i][0]=dp[i+1][0]+q2[dp[i+1][2]];
dp[i][1]=dp[i+1][1];
dp[i][2]=dp[i+1][2]-1;
}
if(i+d<n&&dp[i+d+1][1]>=0)
if(dp[i+d+1][0]+q1[dp[i+d+1][1]]>dp[i][0])
{
dp[i][0]=dp[i+d+1][0]+q1[dp[i+d+1][1]];
dp[i][1]=dp[i+d+1][1]-1;
dp[i][2]=dp[i+d+1][2];
}
if(dp[i][0]==-1)
{
dp[i][0]=dp[i+1][0];
dp[i][1]=dp[i+1][1];
dp[i][2]=dp[i+1][2];
}
}
int ans=0;
for(register int i=1;i<=n;++i)
ans=max(ans,dp[i][0]);
printf("%lld\n",ans);
return 0;
}
```