斜率优化专题4——bzoj 1911: [Apio2010] 特别行动队题解

2020-12-13 01:48

阅读：279

标签：题解 bzoj 斜率优化

【原题】

1911: [Apio2010]特别行动队

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 2134 Solved: 911
[Submit][Status]

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

HINT

soscw.com,搜素材

【分析】只要跟着我前面的题目走，这道题真的是太水了。神马题解都不用参考，公式随便推。

易知方程是f[i]=max(f[j]+A*(sum[i]-sum[j])^2+B*(sum[i]-sum[j])+C)
设k比j优。
f[k]+A(sum[i]-sum[k])^2+B(sum[i]-sum[k])+C>f[j]+A(sum[i]-sum[j])^2+B(sum[i]-sum[j])+C
f[k]-2*A*sum[i]*sum[k]+A*sum[k]^2-B*sum[k]>f[j]-2*A*sum[i]*sum[j]+A*sum[j]^2-B*sum[j]
f[k]-f[j]+A*(sum[k]^2-sum[j]^2)+B*(sum[j]-sum[k])>2*A*sum[i]*(sum[k]-sum[j])
(f[k]-f[j]+A*(sum[k]^2-sum[j]^2)+B*(sum[j]-sum[k]))/2/(sum[k]-sum[j])/A

【代码】

#include
#include
using namespace std;
long long n,a[1000005],f[1000005],q[1000005],sum[1000005],ans,h,t,i,A,B,C,j;
long long M(long long x){return x*x;}
double xie(long long k,long long j)
{
  double temp=(f[k]-f[j]+A*(M(sum[k])-M(sum[j]))+B*(sum[j]-sum[k])+0.0)/2.0/(sum[k]-sum[j])/A;
  return temp;
}
int main()
{
  scanf("%lld",&n);
  scanf("%lld%lld%lld",&A,&B,&C);
  for (i=1;ixie(i,q[t])) t--;  
    q[++t]=i;  
  }  
  printf("%lld",f[n]);
  return 0;
}

斜率优化专题4——bzoj 1911: [Apio2010] 特别行动队题解,搜素材,soscw.com

斜率优化专题4——bzoj 1911: [Apio2010] 特别行动队题解

标签：题解 bzoj 斜率优化

原文地址：http://blog.csdn.net/jiangshibiao/article/details/25079385

上一篇：Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析

下一篇：js中数组和对象的合并

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：斜率优化专题4——bzoj 1911: [Apio2010] 特别行动队题解
文章链接：http://soscw.com/essay/24251.html

亲，登录后才可以留言！

斜率优化专题4——bzoj 1911: [Apio2010] 特别行动队题解

1911: [Apio2010]特别行动队

Description

Input

Output

Sample Input

Sample Output

HINT

评论

热门文章

推荐文章

最新文章

置顶文章

斜率优化专题4——bzoj 1911: [Apio2010] 特别行动队 题解

1911: [Apio2010]特别行动队

Description

Input

Output

Sample Input

Sample Output

HINT

评论

热门文章

推荐文章

最新文章

置顶文章

斜率优化专题4——bzoj 1911: [Apio2010] 特别行动队题解