bzoj 1911 [Apio2010]特别行动队

2021-06-10 05:04

阅读：514

标签：pre efi 前缀和 pac std span c++ for printf

DP+斜率优化

dp[i]表示在前第i个士兵在特别行动队中最后一个时战斗力的最大值

sum[i]表示战斗力的前缀和

答案一定是dp[n]

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

令j优于k，则得到

2*a*sum[i]*(sum[k]-sum[j])>dp[k]+a*sum[k]^2-b*sum[k]-(dp[j]+a*sum[j]^2-b*sum[j])

令f[x]=dp[x]+a*sum[x]^2-b*sum[x]

2*a*sum[i]*(sum[k]-sum[j])>f[k]-f[j]

2*a*sum[i]>(f[k]-f[j])/(sum[k]-sum[j])

用单调队列维护即可

#include #define ll long long
using namespace std;
const ll MAXN=1e6+100;
ll n,a,b,c,sum[MAXN],dp[MAXN];
ll l,r,q[MAXN];
ll f(ll x)
{
    return dp[x]+a*sum[x]*sum[x]-b*sum[x];//如上
}
double xie(ll x,ll y)
{
    return ((double)f(x)-f(y))/((double)sum[x]-sum[y]);//求斜率
}
int main()
{
    scanf("%lld",&n);
    scanf("%lld%lld%lld",&a,&b,&c);
    for (ll i=1;i)
    {
        ll num;
        scanf("%lld",&num);
        sum[i]=sum[i-1]+num;
    }for (ll i=1;i)
    {
        while (l1])>(double)2*a*sum[i])//维护单调队列
          l++;
        dp[i]=dp[q[l]]+a*(sum[i]-sum[q[l]])*(sum[i]-sum[q[l]])+b*(sum[i]-sum[q[l]])+c;
        while (lxie(q[r],q[r-1]))//维护单调队列
          r--;
        r++;
        q[r]=i;
    }
    printf("%lld\n",dp[n]);
}

bzoj 1911 [Apio2010]特别行动队

标签：pre efi 前缀和 pac std span c++ for printf

原文地址：https://www.cnblogs.com/huangchenyan/p/10617889.html

上一篇：解决XP“不是有效Win32程序” 不是改Platform toolset

下一篇：window.onload与$(document).ready() 的区别

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

亲，登录后才可以留言！

bzoj 1911 [Apio2010]特别行动队

DP+斜率优化

评论

热门文章

推荐文章

最新文章

置顶文章