Print Article HDU - 3507 | 斜率dp

把i看成j了，佛系debug一晚上，感觉越来越菜了

题意：
给出N个单词，每个单词有个非负权值Ci，现在要将它们分成连续的若干段，每段的代价为此段单词的权值和的平方，还要加一个常数M,，即。现在想求出一种最优方案，使得总费用之和最小。
分析：

• 注意一开始0要入队
• 注意斜率的比较不能用double，要交叉相乘，考虑到分母不为零
  代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 5e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
int dp[maxn], q[maxn];
int sum[maxn];
int head, tail;

int sq(int n)
{
    return n * n;
}

int getdp(int i, int j)
{
    return dp[j] + sq(sum[i] - sum[j]) + m;
}

int getup(int i, int j)
{
    return dp[i] + sq(sum[i]) - dp[j] - sq(sum[j]);
}

int getdown(int i, int j)
{
    return 2 * (sum[i] - sum[j]);
}

int main()
{
    while(scanf("%d%d", &n, &m) == 2)
    {
        for(int i=1;i<=n;i++)
           scanf("%d",&sum[i]);
        sum[0]=dp[0]=0;
        for(int i=1;i<=n;i++)
           sum[i]+=sum[i-1];
        head=tail=0;
        q[tail]=0;
        for(int i = 1; i <= n; i++)
        {
            while(head<tail &&  getup(q[head+1],q[head])<=sum[i]*getdown(q[head+1],q[head]))
               head++;
            dp[i]=getdp(i,q[head]);
            while(head<tail && getup(i,q[tail])*getdown(q[tail],q[tail-1])<=getup(q[tail],q[tail-1])*getdown(i,q[tail]))
                tail--;
            q[++tail]=i;
        }
        cout << dp[n] << endl;
    }
}