1911: [Apio2010]特别行动队

2021-07-12 18:12

阅读：546

标签：print 优化 def hint limit mil nbsp turn 16px

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 5706 Solved: 2876
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

HINT

技术分享图片

似乎逐渐掌握了斜率优化的规律，，，

 1 #include 2 #include 3 using namespace std;
 4 
 5 #define LL long long
 6 #define sqr(x) ((x)*(x))
 7 const int MAXN=1000005;
 8 
 9 int n,a,b,c;
10 int l,r,q[MAXN];
11 LL f[MAXN],s[MAXN];
12 
13 LL cal(LL x)
14 {
15     return a*sqr(x)+b*x+c;
16 }
17 
18 double slope(int k,int j)
19 {
20     return (double)(f[j]-f[k]+a*(sqr(s[j])-sqr(s[k]))+b*(s[k]-s[j]))/(2*a*(s[j]-s[k]));
21 }
22 
23 int main()
24 {
25     scanf("%d",&n);
26     scanf("%d%d%d",&a,&b,&c);
27     for(int i=1;i)
28     {
29         int x;
30         scanf("%d",&x);
31         s[i]=s[i-1]+x;
32     }
33     for(int i=1;i)
34     {
35         while(l1]);
36         int t=q[l];
37         f[i]=f[t]+cal(s[i]-s[t]);
38         while(l1],q[r])) r--;
39         q[++r]=i;
40     }
41     printf("%lld",f[n]);
42     return 0;
43 }

1911: [Apio2010]特别行动队

标签：print 优化 def hint limit mil nbsp turn 16px

原文地址：https://www.cnblogs.com/InWILL/p/9595401.html

上一篇：mvc方式创建webAPI 解决跨域问题

下一篇：C# 测试代码#if DEBUG使用

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

亲，登录后才可以留言！

1911: [Apio2010]特别行动队

Description

Input

Output

Sample Input

Sample Output

HINT

评论

热门文章

推荐文章

最新文章

置顶文章