70288 - CSP-S第一轮同测模拟卷1-完善程序2
统计题目(材料题)
（2）划分序列：给定长度为n的正整数序列a，需要将其划分为若干个连续段，每段的代价为（段内元素和）的平方加上一个常C，求最小总代价。
01 #include <iostream>
02 using namespace std;
03
04 const int MAXN = 100005;
05 int n;
06 long long C;
07 long long a[MAXN], sum[MAXN];
08 long long dp[MAXN];
09 int q[MAXN], head, tail;
10
11 long long getY(int j) { return ①; }
12 long long getX(int j) { return ②; }
13
14 bool check1(int j1, int j2, int j3) {
15 return (getY(j2) - getY(j1)) * (getX(j3) - getX(j2)) >=
16 (getY(j3) - getY(j2)) * (getX(j2) - getX(j1));
17 }
18
19 bool check2(int j, int i) {
20 return getY(j) - 2 * sum[i] * getX(j) + sum[i] * sum[i] + C
21 >= ③;
22 }
23
24 int main() {
25 cin >> n >> C;
26 for (int i = 1; i <= n; ++i) { cin >> a[i]; sum[i] = sum[i-1] + a[i]; }
27 head = tail = 1;
28 q[1] = 0;
29 dp[0] = 0;
30 for (int i = 1; i <= n; ++i) {
31 while (head < tail && check2(④, i)) head++;
32 int j = q[head];
33 dp[i] = dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) + C;
34 while (head < tail && ⑤) tail--;
35 q[++tail] = i;
36 }
37 cout << dp[n] << endl;
38 return 0;
39 }
关注我们
