关于#程序设计#的问题，如何解决？

Question

Ddcvg. 最小差方和
时间限制：1.0s 内存限制：256.0MB 代码提交间隔：5分钟(现在可以提交)
试题来源：程序设计基础 2013秋 期末考试
问题描述
　　给定n和L，以及n个整数a[i]。
　　要求把a[i]分成连续的若干段。对于每一段，假设其和为S，则其代价为(S-L)^2。
　　整个划分方案的代价定义为每一段代价之和。
　　求所有划分方案中的最小代价。
输入格式
　　第一行两个正整数n和L。
　　第二行n个整数a[i]。
输出格式
　　一行一个非负整数表示最小代价。
样例输入
5 3
-1 2 2 4 -1
样例输出
0
样例说明
　　划分方案为(-1 2 2)以及(4 -1)，两段的代价均为0，总代价为0。
数据规模和约定
　　60%的数据，n<=100，L<=1000;
　　100%的数据，n<=3000，L<=2^20-1，|a[i]|<=100000。

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

const int MAXN = 3005;

int n, L, a[MAXN];
int dp[MAXN];
int sum[MAXN]; // cumulative sum of elements

int cost(int i, int j) {
    int s = sum[j] - sum[i-1];
    int d = s - L;
    return d*d;
}

int main() {
    cin >> n >> L;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = INT_MAX;
        for (int j = 0; j < i; j++) {
            dp[i] = min(dp[i], dp[j] + cost(j+1, i));
        }
    }

    cout << dp[n] << endl;

    return 0;
}

帮帮我

Answer 1

这道题是一个典型的动态规划问题，我们可以用 dp[i] 表示前 i 个数的最小代价，然后考虑如何从 dp[j] 转移过来，其中 j<i。

为了使代价最小，我们应该让前 i 个数尽量少地被分成多个连续段，因此我们枚举最后一段的起点 j，然后计算 j+1 到 i 这一段的和 s，代价即为 (s-L)^2。由于 s 和 L 都是整数，我们可以直接求出代价而不需要用到 sqrt 函数。转移方程如下：

dp[i] = min{dp[j] + (sum[i]-sum[j]-L)^2}, 0≤j<i

其中 sum[i] 表示前 i 个数的和。

最终的答案是 dp[n]，即前 n 个数的最小代价。

时间复杂度是 O(n^2)。由于 n≤3000，因此可以通过本题。