也许更好的阅读体验
(mathcal{Description})
(mathcal{Solution})
30分思路
设(f[i])表示以(i)结尾，划分的区间都合法时，小奇得票数比魔法猪最多多几票
设(sum[i])表示支持情况的前缀和
令(jin[max(i-r,0),max(i-l,0)])
若(sum[i]==sum[j]) 则 (f[i]=max(f[i],f[j]))
若(sum[i] > sum[j]) 则 (f[i]=max(f[i],f[j]+1))
若(sum[i] < sum[j]) 则 (f[i]=max(f[i],f[j]-1))
复杂度(O(n*(r-l+1)))
代码就不贴了
100分思路
考虑优化30分思路，能否用数据结构把((r-l+1))的复杂度优化为(log)级别
用一个权值线段树来维护每一个(sum)值，即权值线段树中的节点的意义为，若该节点表示区间([k,k])(叶子节点),它维护的值是在当前计算的位置的合法区间([max(i-r,0),max(i-l,0)])内，(sum)值为(k)的数的(f)最大是多少
这样我们只要动态地维护权值线段树就可以了，而每当(i)往后移一次，实质上有效区间就是整体往后移了一位，要维护的就只有区间两端的数字，用优先队列维护(sum)的最大(f)值即可
代码
/*******************************
Author:Morning_Glory
LANG:C++
Created Time:2019年06月22日 星期六 08时06分50秒
*******************************/
#include <cstdio>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <queue>
#define mk make_pair
using namespace std;
const int maxn = 1000006;
const int m = 1000001;
const int inf = 10000007;
const char no [] = "Impossible";
//{{{cin 读入优化
struct IO{
template<typename T>
IO & operator>>(T&res){
res=0;
bool flag=false;
char ch;
while((ch=getchar())>'9'||ch<'0') flag|=ch=='-';
while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
if (flag) res=~res+1;
return *this;
}
}cin;
//}}}
int n,l,r;
int sum[maxn],f[maxn];
int val[maxn<<3],pos[maxn<<1],lt[maxn<<3],rt[maxn<<3];
priority_queue < pair<int,int> > q[maxn<<1];
//{{{build(k,l,r)
void build (int k,int l,int r)
{
lt[k]=l,rt[k]=r;
if (l==r){
val[k]=-inf,pos[l]=k;
return ;
}
int mid=(l+r)>>1;
build (k<<1,l,mid);
build (k<<1|1,mid+1,r);
val[k]=max(val[k<<1],val[k<<1|1]);
}
//}}}
//{{{insert(u,v)
void insert (int u,int v)
{
int k=pos[u];
while (k){
val[k]=max(val[k],v);
k>>=1;
}
}
//}}}
//{{{change(u,v)
void change (int u,int v)
{
int k=pos[u];
val[k]=v;
while (k>>=1) val[k]=max(val[k<<1],val[k<<1|1]);
}
//}}}
//{{{query(k,l,r)
int query (int k,int l,int r)
{
if (lt[k]>=l&&rt[k]<=r) return val[k];
if (lt[k]>r||rt[k]<l) return -inf;
int res=-inf;
res=max(res,query(k<<1,l,r));
res=max(res,query(k<<1|1,l,r));
return res;
}
//}}}
int main()
{
cin>>n>>l>>r;
for (int i=1;i<=n;++i) cin>>sum[i],sum[i]+=sum[i-1];
build(1,1,m<<1);
for (int i=1;i<=n;++i) f[i]=-inf;
f[0]=0,q[0].push(mk(0,0));//二元组(f,k)表示f值和位置
for (int i=l;i<=n;++i){
int s=sum[i-l]+m;//防止负数
insert(s,f[i-l]);
q[s].push(mk(f[i-l],i-l));
if (i>r){
s=sum[i-r-1]+m;
while (!q[s].empty()&&i-r>q[s].top().second) q[s].pop();
if(q[s].empty()) change(s,-inf);
else change(s,q[s].top().first);
}
s=sum[i]+m;
f[i]=max(f[i],query(1,1,s-1)+1);
f[i]=max(f[i],query(1,s,s));
f[i]=max(f[i],query(1,s+1,m<<1)-1);
}
if (f[n]<-n) printf("%s
",no);
else printf("%d
",f[n]);
return 0;
}