当前位置: 首页 > news >正文

Luogu P12376「LAOI-12」Calculate 题解 [ 蓝 ] [ 贪心 ] [ 线性 DP ] [ 前缀和优化 ] [ 范德蒙德卷积 ]

Calculate:简单计数 DP。

先考虑 \(\sum_{i = 1}^{p - 1}(a_{i + 1} - a_i)^2\) 的最大值怎么求。利用调整法可以得到结论:每次走当前未选的最大值、最小值交替选一定最优。还有另一种理解方式:注意到两数之差的平方很像欧几里得距离,所以把 \(a_i\) 变成点 \((a_i, a_i)\),那么如果要让起点为 \(1\) 且走过的路径最长,则一定是 \(a_1\to a_n\to a_2\to a_{n - 1}\to a_3\to\cdots\) 的路径最优。

有了贪心结论,又因为是子序列,所以可以将原序列排序以方便计数。此时要我们统计的是这样反复横跳的路径的权值和。

容易设计出一个 DP:\(dp_i\) 表示以 \(i\)最左侧端点,且长度为偶数的路径个数;\(c_i\) 表示以 \(i\) 为最左侧端点,且长度为偶数的路径权值和。从左到右枚举到 \(i\) 时,转移如下:

  • \(dp_{j}\overset{+}{\leftarrow} \sum_{k = j+1}^{i - 1}dp_k\)
  • \(c_j\overset{+}{\leftarrow} \sum_{k = j + 1}^{i - 1}c_k + \sum_{k = j+1}^{i - 1}dp_k\times (a_i - a_k)^2 + (\sum_{k = j+1}^{i - 1}dp_k)\times(a_i - a_j)^2\)

直接转移是 \(O(n^3)\) 的,前缀和优化一下即可做到 \(O(n^2)\)。另一种做法是范德蒙德卷积加上一点数学推导,但是我不会。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 5005;
const ll mod = 998244353;
int n;
ll a[N], dp[N], c[N], ans;
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + n + 1);for(int i = 1; i <= n; i++){ll smdp = 0, smc = 0, smdp2 = 0;for(int j = i - 1; j >= 1; j--){ll oridp = dp[j], oric = c[j];dp[j] = (dp[j] + smdp) % mod;c[j] = (c[j] + smc + smdp2 + smdp * (a[i] - a[j]) % mod * (a[i] - a[j]) % mod) % mod;smdp = (smdp + oridp) % mod;smdp2 = (smdp2 + oridp * (a[i] - a[j]) % mod * (a[i] - a[j]) % mod) % mod;smc = (smc + oric) % mod;dp[j] = (dp[j] + 1) % mod;c[j] = (c[j] + (a[i] - a[j]) * (a[i] - a[j]) % mod) % mod;}}for(int i = 1; i <= n; i++)ans = (ans + c[i]) % mod;cout << ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=35386

相关文章:

  • 方格图路径计数 dp 的反射路径优化
  • 每日反思(2025_10_20)
  • java基础9-面向对象进阶
  • 企业信息化建设的钱都花在哪儿了?
  • 身份运算符
  • 位运算符
  • 关系运算符
  • 赋值运算符
  • 算术运算符
  • Inno Setup 打包脚本模板
  • LCR 155. 将二叉搜索树转化为排序的双向链表
  • 解释这些区块链核⼼概念:区块、交易、Merkle Tree、共识机制(PoW、PoS)、Gas Fee 原理1
  • Claude code cli 的think mode到底是啥?
  • 【VM虚拟机共享主机代理】2025年10月20日可以pass的一些配置
  • 玄机——Linux后门应急
  • 2025/10/20
  • UI弹窗遮罩屏蔽触发事件的处理
  • newDay13
  • 小整数的地址
  • 概率论
  • 一次XFS死锁问题分析
  • P11150 [THUWC 2018] 字胡串
  • 推荐系统与机器学习在会员服务中的应用
  • ManySpeech.MoonshineAsr 使用指南
  • 日志|JAVAWEB|maven
  • QT_基础
  • 2022 ICPC Hangzhou G and 2022 ICPC Jinan
  • C++在类定义内的函数包含static代表什么含义呢?
  • 2025/10/20~2025/?/? 做题笔记 - sb
  • 10-20 Extra-Problem 总结