推广计划和推广单元,无锡百度关键词优化,动漫制作专业属于什么大类,网站套餐到期是什么意思http://www.lydsy.com/JudgeOnline/problem.php?id1911 (题目链接) 题意 给出一个序列#xff0c;将序列分成连续的几段#xff0c;每段的价值为a*s*sb*sc#xff0c;其中a,b,c为给定常数#xff0c;s为这一段中所有数之和。求最大价值和。 Solution 斜率优化。 dp方程1911 (题目链接) 题意 给出一个序列将序列分成连续的几段每段的价值为a*s*sb*sc其中a,b,c为给定常数s为这一段中所有数之和。求最大价值和。 Solution 斜率优化。 dp方程$${f[i]max(f[j]a*(s[i]-s[j])^2b*(s[i]-s[j])c)}$$ 其中${s[i]}$为前缀和${f[i]}$表示从1~i的最大价值。 斜率式$${s[i]*(2*a*s[j])f[i](f[j]-b*s[j]a*s[j]^2)a*s[i]^2b*s[i]c}$$ 所以决策${j}$映射到平面直角坐标系上就是${(2*a*s[j],f[j]-b*s[j]a*s[j]^2)}$。斜率${s[i]}$为正且单增横坐标${2*a*s[j]}$单减${a}$小于0${s[j]}$单增所以单调队列里面的点长成这样 细节 开long long。 代码 // bzoj1911
#includealgorithm
#includeiostream
#includecstdlib
#includecstring
#includecstdio
#includecmath
#define LL long long
#define inf 1e18
#define Pi acos(-1.0)
#define free(a) freopen(a.in,r,stdin),freopen(a.out,w,stdout);
using namespace std;const int maxn1000010;
LL f[maxn],s[maxn],a,b,c;
int n,q[maxn];double slope(int i,int j) {return (double)((f[i]-b*s[i]a*s[i]*s[i])-(f[j]-b*s[j]a*s[j]*s[j]))/(double)((2*a*s[i])-(2*a*s[j]));
}
int main() {scanf(%d,n);scanf(%lld%lld%lld,a,b,c);for (int i1;in;i) scanf(%lld,s[i]),s[i]s[i-1];int l1,r1;q[1]0;for (int i1;in;i) {while (lr slope(q[l],q[l1])s[i]) l;f[i]f[q[l]]a*(s[i]-s[q[l]])*(s[i]-s[q[l]])b*(s[i]-s[q[l]])c;while (lr slope(q[r-1],q[r])slope(q[r],i)) r--;q[r]i;}printf(%lld,f[n]);return 0;
}转载于:https://www.cnblogs.com/MashiroSky/p/6013532.html
