简答题 偏难
#22102

day2-2 划分

day2-2 划分


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;vector&gt; #include &lt;climits&gt; 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", &amp;n, &amp;type);     // 读取或生成数组a     if (type == 0) {         for (int i = 0; i &lt; n; ++i) {             scanf("%lld", &amp;a[i]);         }     } else {         ll x, y, z, b1, b2;         int m;         scanf("%lld%lld%lld%lld%lld%d", &amp;x, &amp;y, &amp;z, &amp;b1, &amp;b2, &amp;m);         vector&lt;ll&gt; b(n + 2);  // 1-based索引         b[1] = b1;         if (n &gt;= 2) b[2] = b2;         for (int i = 3; i &lt;= n; ++i) {             b[i] = (x * b[i - 1] + y * b[i - 2] + z) % (1LL &lt;&lt; 30);         }         int prev_p = 0;         for (int j = 0; j &lt; m; ++j) {             int p, l, r;             scanf("%d%d%d", &amp;p, &amp;l, &amp;r);             ll len = r - l + 1;             for (int i = prev_p + 1; i &lt;= p &amp;&amp; i &lt;= n; ++i) {                 a[i - 1] = (b[i] % len) + l;             }             prev_p = p;         }     }     // 计算前缀和     sum[0] = 0;     for (int i = 1; i &lt;= n; ++i) {         sum[i] = sum[i - 1] + a[i - 1];     }     // 初始化DP     dp[0] = 0;     last[0] = 0;  // 前0个元素没有段,用0作为初始值     for (int i = 1; i &lt;= n; ++i) {         dp[i] = INF;         // 寻找最佳的j,j &lt; i         for (int j = 0; j &lt; i; ++j) {             ll current_sum = sum[i] - sum[j];             // 关键条件:当前段的和 &gt;= 前一段的和             if (current_sum &gt;= last[j]) {                 ll candidate = dp[j] + current_sum * current_sum;                 if (candidate &lt; 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,计算当前段和并检查非递减条件,更新最小平方和及最后一段的和。