洛谷 P5336 [THUSC2016]成绩单
2021/10/2 23:14:35
本文主要是介绍洛谷 P5336 [THUSC2016]成绩单,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Description
洛谷传送门
Solution
区间dp
状态定义
根据套路,我们定义 \(dp[i][j]\) 表示取走区间 \([i, j]\) 的最小花费。
但是只有区间范围似乎并不好转移,因为我们也不知道区间最大值以及最小值是多少。
所以我们再定义一个 \(f[i][j][x][y]\) 数组,表示区间 \([i, j]\) 中所有数在区间 \([x, y]\)时,需要的最小花费。
注意:这里 \(f[i][j][x][y]\) 中不一定 \([i, j]\) 中的最小值和最大值就是 \(x\) 和 \(y\)。
转移
这里还要进行分类讨论:
- 直接合并 \(j\) 和 \([i, j - 1]\) 或合并 \(i\) 和 \([i + 1, j]\),那么转移方程就是
f[i][j][min(x, a[j])][max(y, a[j])] = min(f[i][j][min(x, a[j])][max(y, a[j])], f[i][j - 1][x][y]); f[i][j][min(x, a[i])][max(y, a[i])] = min(f[i][j][min(x, a[i])][max(y, a[i])], f[i + 1][j][x][y]);
- 枚举断点 \(k\),先把 \([i, k]\) 合并好之后再和 \([k + 1, j]\) 合并(此时 \([k + 1, j]\) 还没有合并),或先把 \([k + 1, j]\) 合并好之后再和 \([i, k]\) 合并(同理)。
for(ll k = i; k < j; k++) f[i][j][x][y] = min(f[i][j][x][y], min(f[i][k][x][y] + dp[k + 1][j], f[k + 1][j][x][y] + dp[i][k]));
不过好像只转移同一个方向的就够了,不知道为什么 \(QwQ\)。
注意开 \(long \ long\),以及要先进行离散化。
Code
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #define ll long long using namespace std; const ll N = 55; ll n, A, B; ll a[N], b[N]; ll f[N][N][N][N], dp[N][N]; signed main(){ scanf("%lld%lld%lld", &n, &A, &B); for(ll i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i]; sort(b + 1, b + 1 + n); ll tot = unique(b + 1, b + 1 + n) - b - 1; memset(f, 0x3f, sizeof(f)); memset(dp, 0x3f, sizeof(dp)); for(ll i = 1; i <= n; i++){ a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b; f[i][i][a[i]][a[i]] = 0; dp[i][i] = A; } for(ll len = 2; len <= n; len++) for(ll i = 1; i + len - 1 <= n; i++){ ll j = i + len - 1; for(ll x = 1; x <= tot; x++) for(ll y = 1; y <= tot; y++){ f[i][j][min(x, a[j])][max(y, a[j])] = min(f[i][j][min(x, a[j])][max(y, a[j])], f[i][j - 1][x][y]); f[i][j][min(x, a[i])][max(y, a[i])] = min(f[i][j][min(x, a[i])][max(y, a[i])], f[i + 1][j][x][y]); for(ll k = i; k < j; k++) f[i][j][x][y] = min(f[i][j][x][y], min(f[i][k][x][y] + dp[k + 1][j], f[k + 1][j][x][y] + dp[i][k])); } for(ll x = 1; x <= tot; x++) for(ll y = 1; y <= tot; y++) dp[i][j] = min(dp[i][j], f[i][j][x][y] + A + B * (b[y] - b[x]) * (b[y] - b[x])); } printf("%lld\n", dp[1][n]); return 0; }
End
这篇关于洛谷 P5336 [THUSC2016]成绩单的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-29document对象教程:新手入门指南
- 2024-09-29端到端的 AWS DevOps 项目:使用 ECR 和 RDS 的 ECS Fargate 的 CI/CD 管道
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享