题意: 给你一串数, 然后有一个价值计算公式, 每次只能连续输出一段, 问输出所有数的总价值最小是多少
思路: 斜率优化, 但我不知道为什么写成 slop 就不对, 可怜我的斜率优化板子, 又要该了, 其他没什么, 简单的推一下是下凸包, 没什么其他的了
代码:
- #include <set>
- #include <map>
- #include <queue>
- #include <stack>
- #include <math.h>
- #include <vector>
- #include <string>
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #include <iostream>
- #include <algorithm>
- #define zero(a) fabs(a)<eps
- #define max( x, y ) ( ((x)> (y)) ? (x) : (y) )
- #define min( x, y ) ( ((x) <(y)) ? (x) : (y) )
- #define lowbit(x) (x&(-x))
- #define debug(a) cerr<<#a<<"=="<<a<<endl
- typedef long long ll;
- const double pi=acos(-1.0);
- const double eps=1e-8;
- const int inf=0x3f3f3f3f;
- const ll linf=0x3f3f3f3f3f3f3f3f;
- using namespace std;
- const int maxn=500000+7;
- int a[maxn],dp[maxn],pre[maxn];
- int que[maxn],l,r;
- int getUP(int j,int k)
- {
- return dp[j]+pre[j]*pre[j]-(dp[k]+pre[k]*pre[k]);
- }
- int getDOWN(int j,int k)
- {
- return 2*(pre[j]-pre[k]);
- }
- int main()
- {
- int n,m;
- while(~scanf("%d%d",&n,&m)){
- l=1,r=0;
- pre[0]=0;
- for(int i=1;i<=n;i++) scanf("%d",&a[i]),pre[i]=pre[i-1]+a[i];
- dp[0]=0;
- que[++r]=0;
- for(int i=1;i<=n;i++){
- while(l<r&&getUP(que[l+1],que[l])<=getDOWN(que[l+1],que[l])*pre[i])l++;
- int j=que[l];
- dp[i]=dp[j]+(pre[i]-pre[j])*(pre[i]-pre[j])+m;
- while(l<r&&getUP(que[r],que[r-1])*getDOWN(i,que[r])>=getUP(i,que[r])*getDOWN(que[r],que[r-1])) r--;
- que[++r]=i;
- }
- printf("%d\n",dp[n]);
- }
- return 0;
- }
- hdu 3507 Print Article(斜率优化)
来源: http://www.bubuko.com/infodetail-2546485.html