本文共 1899 字，大约阅读时间需要 6 分钟。

题目大意：就是那个公式了

解题思路： 以下参考了

设dp[i]为前i个的和 则dp[i] = min(dp[j] + (sum[i] - sum[j]) ^ 2) 设j < k,则k点比j点更优，则 dp[j] + (sum[i] - sum[j]) ^ >= dp[k] + (sum[i] - sum[k]) ^ 2 化简得 dp[j] + sum[i] ^ 2 + sum[j] ^ 2 - 2 * sum[i] * sum[j] >= dp[k] + sum[i] ^ 2 + sum[k] ^ 2 -2 * sum[i] * sum[k]

即sum[i] >= (dp[k] + sum[k] ^ 2 - dp[j] - sum[j] ^ 2) / (sum[k] - sum[j])

现在假设yj = dp[j] - sum[j] ^ 2, xj = sum[j] 则上面不等式变为(yk - yj) / (xk - xj) <= sum[i] 随着i的增大，sum[i]是递增的 所以我们可以看出以下两点：我们令g[k,j]=(yk-yj)/(xk-xj)

第一：如果上面的不等式成立，那就说k比j优，而且随着i的增大上述不等式一定是成立的，也就是对i以后算DP值时，k都比j优。那么j就是可以淘汰的。

第二：如果 k < j < i 而且 g[k, j] > g[i, k] 那么 k 是可以淘汰的。

假设 g[i, k] < sum[i]就是i比k优，那么k没有存在的价值

相反如果 g[i, k] > sum[i] 那么同样有 g[k, j] > sum[i] 那么 j比 k优 那么 k 是可以淘汰的

所以这样相当于在维护一个下凸的图形，斜率在逐渐增大。

通过一个队列来维护。

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N = 5000010;int dp[N], sum[N], que[N];int n, m;void init() {    sum[0] = dp[0] = 0;    for (int i = 1; i <= n; i++)        scanf("%d", &sum[i]);    for (int i = 1; i <= n; i++)        sum[i] += sum[i - 1];}int getDP(int i, int j) {    return dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) + m;} int getDown(int j, int k) {    return 2 * (sum[j] - sum[k]);}int getUp(int j, int k) {    return dp[j] + sum[j] * sum[j] - (dp[k] + sum[k] * sum[k]); }void solve() {    int head , tail;    head = tail = 0;    que[tail++] = 0;    for (int i = 1; i <= n; i++) {        while (head + 1 < tail && getUp(que[head + 1], que[head]) <= sum[i] * getDown(que[head + 1], que[head]))             head++;        dp[i] = getDP(i, que[head]);        while (head + 1 < tail && getUp(i, que[tail - 1]) * getDown(que[tail - 1], que[tail - 2]) <= getUp(que[tail - 1], que[tail - 2]) * getDown(i, que[tail - 1]))            tail--;        que[tail++] = i;    }    printf("%d\n", dp[n]);}int main() {    while (scanf("%d%d", &n, &m) != EOF) {        init();        solve();    }    return 0;}
     
    
   

转载地址：https://blog.csdn.net/L123012013048/article/details/48946999 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！