bzoj1911: [Apio2010]特别行动队

2021-04-01 20:27

阅读：476

标签：sum 两种方法技术分享 clu 分享 string == isp turn

题目链接

题解

首先，状态转移方程
\(f_i = max(f_j+A(S_i-S_j)^2+B(S_i-S_j)+C)\)
在这里总结一下推斜率优化的两种方法吧

直接推呀:

设\(j且\(j\)比\(k\)优。
\[f_j+A(S_i-S_j)^2+B(S_i-S_j)+C>f_k+A(S_i-S_k)^2+B(S_i-S_k)+C\]
\[f_j-f_k+A(2S_i-S_j-S_k)*(S_k-S_j)+B(S_k-S_j)>0\]
\[f_j+S_j^2-2AS_iS_j-BS_j >f_k+S_k^2-2AS_iS_k-BS_k\]
设\(G_j=f_j+AS_j^2-BS_j\),\(H_j=-2AS_j\)
得到
\(\frac{G_j-G_k}{H_j-H_k}

找直线解析式

技术分享图片

代码

#include
#include
#include 
#define LL long long
inline LL read() { 
    LL x = 0,f = 1;
    char c = getchar(); 
    while(c '0' || c > '9'){ if(c == '-')f = -1; c = getchar();}  
    while(c '9' && c >= '0')x = x * 10 + c - '0',c = getchar(); 
    return x * f; 
} 

const int maxn = 1000007;
LL n,a,b,c; 
LL sum[maxn]; 
LL dp[maxn];  
LL Y (int i) { return dp[i] + a * sum[i] * sum[i] - b * sum[i]; } 
LL X (int i) { return  sum[i]; } 
double slop(int i,int j)  { return 1.0 * (Y(i) - Y(j)) / (X(i) - X(j));  }  
int q[maxn]; 
int main() { 
    n = read(),a = read(),b = read(),c = read(); 
    for(int i = 1;i 1]; 
    for(int l = 0,r = 0,i = 1;i while(l 1]) > 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); 
        dp[i] = -(2 * a * sum[i] * X(q[l]) - Y(q[l]) - a * sum[i] * sum[i] - b * sum[i] - c); 
        while(l 1],q[r]) "%lld\n",dp[n]); 
    return 0; 
}

bzoj1911: [Apio2010]特别行动队

标签：sum 两种方法技术分享 clu 分享 string == isp turn

原文地址：https://www.cnblogs.com/sssy/p/9230914.html

上一篇：c#在类里不能使用Response解决方法

下一篇：Windows 10激活

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

亲，登录后才可以留言！

bzoj1911: [Apio2010]特别行动队

题目链接

题解

直接推呀:

找直线解析式

代码

评论

热门文章

推荐文章

最新文章

置顶文章