简答题
偏难
#22102
day2-2 划分
day2-2 划分



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10; // 调整为更常见的测试规模,可根据需要扩大
const ll INF = LLONG_MAX / 2;
ll a[MAXN];
ll sum[MAXN];
ll dp[MAXN]; // dp[i]表示前i个元素的最小平方和
ll last[MAXN]; // last[i]表示前i个元素最后一段的和
int main() {
int n, type;
scanf("%d%d", &n, &type);
// 读取或生成数组a
if (type == 0) {
for (int i = 0; i < n; ++i) {
scanf("%lld", &a[i]);
}
} else {
ll x, y, z, b1, b2;
int m;
scanf("%lld%lld%lld%lld%lld%d", &x, &y, &z, &b1, &b2, &m);
vector<ll> b(n + 2); // 1-based索引
b[1] = b1;
if (n >= 2) b[2] = b2;
for (int i = 3; i <= n; ++i) {
b[i] = (x * b[i - 1] + y * b[i - 2] + z) % (1LL << 30);
}
int prev_p = 0;
for (int j = 0; j < m; ++j) {
int p, l, r;
scanf("%d%d%d", &p, &l, &r);
ll len = r - l + 1;
for (int i = prev_p + 1; i <= p && i <= n; ++i) {
a[i - 1] = (b[i] % len) + l;
}
prev_p = p;
}
}
// 计算前缀和
sum[0] = 0;
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + a[i - 1];
}
// 初始化DP
dp[0] = 0;
last[0] = 0; // 前0个元素没有段,用0作为初始值
for (int i = 1; i <= n; ++i) {
dp[i] = INF;
// 寻找最佳的j,j < i
for (int j = 0; j < i; ++j) {
ll current_sum = sum[i] - sum[j];
// 关键条件:当前段的和 >= 前一段的和
if (current_sum >= last[j]) {
ll candidate = dp[j] + current_sum * current_sum;
if (candidate < dp[i]) {
dp[i] = candidate;
last[i] = current_sum;
}
}
}
}
printf("%lld\n", dp[n]);
return 0;
}</pre><p><br/></p>
解析
方法思路
1、动态规划状态定义:dp[i] 表示前 i 个元素的最小平方和,last[i] 表示前 i 个元素划分的最后一段的和。
2、状态转移:对于每个 i,寻找所有 j < i 使得 sum[i] - sum[j] >= last[j](保证当前段和 >= 前一段和),则 dp[i] = min(dp[j] + (sum[i]-sum[j])²),同时更新 last[i] = sum[i]-sum[j]。
3、优化策略:利用前缀和的单调性,维护有效候选 j 的集合,避免不必要的计算。
代码解释
1、明确判断条件 current_sum >= last[j],确保当前段的和大于等于前一段的和,严格满足非递减要求。
2、动态规划初始化:dp[0] = 0 表示空序列的平方和为 0,last[0] = 0 作为初始参考值。
3、状态转移:对每个位置 i,遍历所有可能的前一段结束位置 j,计算当前段和并检查非递减条件,更新最小平方和及最后一段的和。