【题解】[APIO2010]特别行动队

2021-03-07 22:27

阅读：507

标签：sign 设计 sig 必须 fine clu mes 等于 line

Link

题目大意：一段区间的贡献是\(ax^2+bx+c,x=\sum v\),求一个划分让总区间的价值最大。分段必须连续。

\(\text{Solution:}\)

设计\(dp[i]\)表示前\(i\)个人的最佳划分价值。那么有转移：

\[dp[i]=\max_{j

显然\(n^2\)的\(dp.\)

搞一下柿子，令\(sum_i\)表示\([1,i]\)的和。

\[dp[i]=dp[j]+a(sum[i]-sum[j])^2+b(sum[i]-sum[j])+c \]

\[dp[i]=dp[j]+a(sum[i]^2+sum[j]^2-2sum[i]sum[j])+bsum[i]-bsum[j]+c \]

\[dp[i]=dp[j]+asum[i]^2+asum[j]^2-2asum[i]sum[j]+bsum[i]-bsum[j]+c \]

\[dp[j]+asum[j]^2-bsum[j]=2asum[i]sum[j]+dp[i]-c-bsum[i]-asum[i]^2 \]

此时\(y=dp[j]+asum[j]^2-bsum[j],k=2asum[i],x=sum[j],b=dp[i]-c-bsum[i]-asum[i]^2\)最大化截距维护上凸壳即可。

#include
using namespace std;
#define int long long
int n,A,B,C,sum[2000010],v[2000010];
int tail,head,q[2000010],dp[2000010];
int Y(int x){return dp[x]+A*sum[x]*sum[x]-B*sum[x];}
int X(int x){return sum[x];}
long double slope(int x,int y){return (long double)(Y(y)-Y(x))/(X(y)-X(x));}
int cost(int i,int j){return A*(sum[i]-sum[j])*(sum[i]-sum[j])+B*(sum[i]-sum[j])+C;}
signed main(){
	/*
	dp[j]+Asum[j]^2-Bsum[j]=2Asum[i]sum[j]+dp[i]-Asum[i]^2-Bsum[i]-C
	y=dp[j]+Asum[j]^2-Bsum[j],k=2Asum[i],x=sum[j],b=dp[i]-Asum[i]^2-Bsum[i]-C
	*/
	scanf("%lld%lld%lld%lld",&n,&A,&B,&C);
	for(int i=1;i=2.0*A*sum[i])head++;
		dp[i]=dp[q[head]]+cost(i,q[head]);
		while(head

值得一提的是，原本在写进队出队判断的时候带上等于是错的，后来发现是精度被卡了。所以尽量用\(\text{long double.}\)

【题解】[APIO2010]特别行动队

标签：sign 设计 sig 必须 fine clu mes 等于 line

原文地址：https://www.cnblogs.com/h-lka/p/12814051.html

上一篇：windows核心编程--2、windows的画笔画刷以及一些简单的应用

下一篇：WPF 打印操作之PrintDialog

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

亲，登录后才可以留言！

【题解】[APIO2010]特别行动队

评论

热门文章

推荐文章

最新文章

置顶文章