思路:dp[i]表示到第i个点为结尾能获得的最大值,那么dp[i]=h[i]*h[i]+dp[i-x]-h[i-x];(i-l<=x<=i);那么我们可以转换下,以dp[i]-h[i]为新的权值,动态方程就变成了dp[i]=dp[i-x]+h[i]*h[i](i-l<=x<=i);只要找到最大的dp[i-x]就可以了。可以用线段树维护。

#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define Maxn 100010
#define Maxm 80002
#define LL __int64
#define Abs(x) ((x)>0?(x):(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define inf 10000000
#define lowbit(x) (x&(-x))
#define clr(x,y) memset(x,y,sizeof(x))
#define Mod 1000000007
using namespace std;
int h[Maxn],sorted[Maxn];
int r[Maxn];
LL dp[Maxn],ans;
struct Tree{
int l,r;
LL Max;
int mid(){
return (l+r)>>;
}
}tree[Maxn*];
int cmp(int a,int b)
{
if(sorted[a]==sorted[b])
return b<a;
return sorted[a]<sorted[b];
}
void BuildTree(int l,int r,int po)
{
tree[po].l=l,tree[po].r=r,tree[po].Max=-;
if(l==r) return ;
int mid=tree[po].mid();
BuildTree(l,mid,lson(po));
BuildTree(mid+,r,rson(po));
}
void update(int i,LL val,int po)
{
if(tree[po].l==tree[po].r){
tree[po].Max=val;
return ;
}
int mid=tree[po].mid();
if(i<=mid)
update(i,val,lson(po));
else
update(i,val,rson(po));
tree[po].Max=max(tree[lson(po)].Max,tree[rson(po)].Max);
}
void query(int i,int po)
{
if(i==)
return ;
if(tree[po].r==i){
ans=max(ans,tree[po].Max);
return ;
}
int mid=tree[po].mid();
if(i<=mid)
query(i,lson(po));
else{
query(mid,lson(po));
query(i,rson(po));
}
}
int main()
{
int t,i,j,Case=,n,l;
scanf("%d",&t);
while(t--){
clr(dp,-);
scanf("%d%d",&n,&l);
for(i=;i<=n;i++){
scanf("%d",h+i);
sorted[i]=h[i];
}
for(i=;i<=n;i++) r[i]=i;
sort(r+,r+n+,cmp);
int pos[Maxn];
for(i=;i<=n;i++) pos[r[i]]=i;
BuildTree(,n,);
for(i=;i<=n;i++){
ans=-;
query(pos[i]-,);
if(i<=l)
dp[i]=(LL)h[i]*h[i];
if(ans>=)
dp[i]=max(dp[i],(LL)h[i]*h[i]+ans);
update(pos[i],dp[i]-(LL)h[i],);
if(i-l>)
update(pos[i-l],-,);
}
printf("Case #%d: ",++Case);
if(dp[n]<)
printf("No solution\n");
else
printf("%I64d\n",dp[n]);
}
return ;
}
04-26 17:06
查看更多