Codeforces13C–Sequence (区间DP)
2024-10-21 12:40:27
题目大意
给定一个含有N个数的序列,要求你对一些数减掉或者加上某个值,使得序列变为非递减的,问你加减的值的总和最少是多少?
题解
一个很显然的结果就是,变化后的每一个值肯定是等于原来序列的某个值,因为只需要变为非递减的,所以对于某个数要么不变,要么变成左右附件的某个值。这样我们就可以根据前述条件得出DP方程了:dp[i][j]=min(dp[i][j-1],dp[i-1][j]+|a[i]-b[j]|)(a为原序列,b为排序后的序列),方程的意思是,把序列前i个数变为非递减序列并且以不超过b[j]的值结尾的最小花费,那么它要么是以不超过b[j-1]结尾的最小花费,或者是刚好以b[j]结尾的最小花费
代码:
1 #include <algorithm>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <cstdlib>
6 using namespace std;
7 #define MAXN 5005
8 #define INF 0x3f3f3f3f
9 typedef long long LL;
10 LL dp[MAXN],a[MAXN],b[MAXN];
11 int main()
12 {
13 int n;
14 scanf("%d",&n);
15 for(int i=1;i<=n;i++) scanf("%I64d",&a[i]),b[i]=a[i];
16 sort(b+1,b+n+1);
17 for(int i=1;i<=n;i++)
18 for(int j=1;j<=n;j++)
19 {
20 if(j==1)dp[j]+=abs(a[i]-b[j]);
21 else
22 dp[j]=min(dp[j-1],dp[j]+abs(a[i]-b[j]));
23 }
24 printf("%I64d\n",dp[n]);
25 return 0;
26 }
原创博客:https://www.cnblogs.com/zjbztianya/archive/2013/09/06/3305003.html
最新文章
- JSON字符串和JS对象之间的转换
- OC 类方法,对象方法,构造方法以及instancetype和id的异同
- Android ImageCache图片缓存,使用简单,支持预取,支持多种缓存算法,支持不同网络类型,扩展性强
- php中count获取多维数组长度的方法
- linq 学习笔记(一)
- 一道js题(引用类型、基本类型、包装对象、函数赋值)
- android学习18——对PathMeasure中getPosTan的理解
- Markdown简明教程
- MyDAL - in &;&; not in 条件 使用
- 自定义InputFormat和OutputFormat案例
- Xamarin.Forms FlexLayout 布局扩展+ 模板扩展+弹性换行
- Win10系列:C#应用控件进阶4
- html5手势操作与多指操作封装与Canvas图片裁切实战
- docker部署maven私有仓库 nexus3
- base64 压缩图片
- vue - vue-cli脚手架项目中组件的使用
- electron-vue 项目搭建的地址
- C语言实现---学生成绩管理系统
- labview之连接MySQL数据库
- (转)Nginx图片服务器
热门文章
- Windows10下Canvas对象获得屏幕坐标不正确的原因排查与处理
- STM32F207时钟系统解析
- [阿里DIEN] 深度兴趣进化网络源码分析 之 Keras版本
- Linux 三剑客之 grep 使用详解
- Profile Guided Optimization Link Time Optimization
- 不占用额外内存空间能否做到 将图像旋转90度 N &;#215; N矩阵表示的图像,其中每个像素的大小为4字节
- gitignore 不起作用的解决办法 不再跟踪 让.gitignore生效,跟踪希望被跟踪的文件
- Kubernetes TensorFlow 默认 特定 集群管理器 虚拟化技术
- JPEG解码——(3)文件头解析
- 快速计算C(n,r)