POJ 3666 Making the Grade【DP】
2024-08-30 14:52:38
读题堪忧啊,敲完了才发现理解错了。。理解题必须看样例啊!!
题目链接:
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=110495#problem/S
题意:
给定序列,做出最少的改变,使得新的序列单调非增或者或单调非减。
分析:
先考虑单调非增。
如果后一个元素比前一个小,那么最少改变的情况就是让他和前一个元素相等。如果比前一个元素大或者相等,则不需做出改变。
仔细想想就可以发现其实最后的序列就是由原始数组的元素组成。
那么我们先对原始数组排个序,
设dp[i][j]为考虑第i个位置,放排序后的第j个元素的改变量。
最初按照二维想的,然后直接压缩成一维的。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define sa(a) scanf("%d", &a)
#define sal(a) scanf("%I64d", &a)
const int maxn = 2000 + 5, INF = 0x3f3f3f3f;
int a[maxn], na[maxn];
long long dp[maxn];
int main (void)
{
int n;sa(n);
for(int i = 0; i < n; i++) {
sa(a[i]);na[i] = a[i];}
sort(na, na + n);
memset(dp, 0x3f, sizeof(dp));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
dp[j] = min(dp[j], dp[j - 1] + abs(a[j] - na[i]));
}
}
long long ans = dp[n - 1];
memset(dp, 0x3f, sizeof(dp));
for(int i = n - 1; i >= 0; i--){
for(int j = 0; j < n; j++){
dp[j] = min(dp[j], dp[j - 1] + abs(a[j] - na[i]));
}
}
printf("%I64d\n",min(ans, dp[n - 1]));
return 0;
}
最新文章
- mysql 添加用户并授权
- 【转】如何确定Kafka的分区数、key和consumer线程数
- Problems running django-admin
- 深入Mysql 导入导出
- GB2312 简体中文编码表
- Java基础知识强化之IO流笔记05:try...catch...finally包含的代码是运行期的
- g++ error: expected ‘)’ before ‘*’ token
- 2014第3周六升级win8.1
- elasticsearch的javaAPI之query
- OCA读书笔记(16) - 执行数据库恢复
- 【Unity与23种设计模式】解释器模式(Interpreter)
- 深入理解Java虚拟机阅读心得(一)
- AGC027 B - Garbage Collector 枚举/贪心
- 第二阶段——个人工作总结DAY01
- Hive Tunning(三) 最佳实践
- [转]win server 2003 + IIS 6 搭建MVC 运行环境
- Linux命令-目录处理命令:ls
- [转]C#在WinForm下使用HttpWebRequest上传文件并显示进度
- hdu2112HDU Today(floyd+map数组对字符串的应用)
- 第15章—数据库连接池(DBCP2)