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

题目大意：给你N个数，要求你分成M个部分，每部分的得分为，假设该部分为i, j, k, 那么的分就为i * j + i * k + j * k

问划分后，至少能得多少分

解题思路：设dp[i][j]为前面i个数，分成j个部分能得到得最小得分

得转移方程dp[i][j] = dp[k][j - 1] + cost[i] - cost[k] - (sum[i] - sum[k]) * sum[k] 这里的cost[i]表示的是前i个数为1个部分的情况下所能得到的分 因为cost[i] - cost[k]后，还多了sum[k] * (sum[i] - sum[k])，所以后面要减去 现在设l > k，且在l比j更优 则dp[k][j - 1] + cost[i] - cost[k] - sum[k] * (sum[i] - sum[k]) >= dp[l][j - 1] + cost[i] - cost[l] - sum[l] * (sum[i] - sum[l]) 化简可得 sum[i] >= (dp[l][j - 1] - cost[l] + sum[l] ^ 2 - dp[k][j - 1] + cost[k] - sum[k] ^ 2) / (sum[l] - sum[k])

这样就得到斜率优化的式子了

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

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