codeforces C. Sonya and Problem Wihtout a Legend(dp or 思维)
2024-09-01 05:46:19
题目链接:http://codeforces.com/contest/713/problem/C
题解:这题也算是挺经典的题目了,这里附上3种解法优化程度层层递进,还有这里a[i]-i<=a[i+1]-(i+1),处理一下。
首先是最基础的dp[i][j]前i位最大值为j的最小值为多少。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define inf 0X3f3f3f3f
using namespace std;
const int M = 3e3 + 10;
typedef long long ll;
ll dp[M][M] , a[M] , b[M];
int main() {
int n;
scanf("%d" , &n);
memset(b , 0 , sizeof(b));
for(int i = 1 ; i <= n ; i++) scanf("%lld" , &a[i]) , b[i] = a[i] = a[i] - i;
memset(dp , inf , sizeof(dp));
int cnt = 0;
b[0] = -1000000000000000;
sort(b + 1 , b + 1 + n);
for(int i = 1 ; i <= n ; i++) {
if(b[i] != b[i - 1]) b[++cnt] = b[i];
}
for(int i = 1 ; i <= cnt ; i++) dp[0][i] = 0;
for(int i = 1 ; i <= n ; i++) {
ll tmp = dp[i - 1][1];
for(int j = 1 ; j <= cnt ; j++) {
tmp = min(tmp , dp[i - 1][j]);
dp[i][j] = tmp + abs(a[i] - b[j]);
}
}
ll ans = 1000000000000000;
for(int i = 1 ; i <= cnt ; i++) {
ans = min(ans , dp[n][i]);
}
printf("%lld\n" , ans);
return 0;
}
然后是滚动优化注意那个dp的转移方式只和上一个状态有关系所以可以用滚动优化dp[2][M],这样优化了空间
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define inf 0X3f3f3f3f
using namespace std;
typedef long long ll;
const int M = 3e3 + 10;
int a[M] , b[M];
ll dp[2][M];
int main() {
int n , m;
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i++) scanf("%d" , &a[i]) , a[i] -= i , b[i] = a[i];
m = 0;
sort(b + 1 , b + 1 + n);
b[0] = -1e9 - 10;
for(int i = 1 ; i <= n ; i++) {
if(b[i] != b[i - 1]) b[++m] = b[i];
}
memset(dp , inf , sizeof(dp));
for(int i = 1 ; i <= n ; i++) dp[0][i] = 0;
for(int i = 1 ; i <= n ; i++) {
ll tmp = dp[(i - 1) % 2][1];
for(int j = 1 ; j <= m ; j++) {
tmp = min(tmp , dp[(i - 1) % 2][j]);
dp[i % 2][j] = tmp + abs(a[i] - b[j]);
}
}
ll Min = 1e15 + 10;
for(int i = 1 ; i <= m ; i++) Min = min(Min , dp[n % 2][i]);
printf("%lld\n" , Min);
return 0;
}
最后是最强的优化复杂度可以到达O(nlogn),就是用优先队列来优化,其实这个具体去证明也不太好证明但是理解还是好理解的具体画一下图意会一下
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
priority_queue<int>q;
int main() {
int n;
cin >> n;
long long ans = 0;
for(int i = 1 ; i <= n ; i++) {
int x;
scanf("%d" , &x);
x -= i;
q.push(x);
if(q.top() > x) {
int t = q.top();
q.pop();
ans += t - x;
q.push(x);
}
}
cout << ans << endl;
return 0;
}
最新文章
- 搜索引擎Solr系列(二): Solr6.2.1 从MySql中导入数据
- mysql 5.7.11 yum 安装步骤
- oricle数据库关于定时
- loadrunner获取本机的机器名称
- XE6移动开发环境搭建之IOS篇(1):准备安装材料(有图有真相)
- codeforces 361 B - Mike and Shortcuts
- [整理]C#反射(Reflection)详解
- 提示“正尝试安装的adobe flash player不是最新版本”的解决方法
- SpringMVC类型转换、数据绑定详解[附带源码分析]
- SQL SERVER 复制相关存储过程
- [百度空间] [转]关于Direct3D多窗口编程的一篇翻译
- mysql开启外联方法
- MongoDB自定义函数部分 定义及引用
- BZOJ 3875: [Ahoi2014]骑士游戏
- SVN目录对号图标(更新、冲突)不显示
- 【Android Developers Training】 22. 与其他fragment通信
- net+Oracle开发过程中遇到的小问题
- 天津联通新兴ICT业务工程师面试经历
- Java笔记(二十一) 动态代理
- 配置微信jssdk自定义分享
热门文章
- LinkedList源码分析(jdk1.8)
- Js面向对象原型~构造函数
- 当面对会反制遭破解装置的App该如何顺利提取数据
- DHCP服务器的搭建及抓包分析DHCP的实现
- mcrp 对接软件换
- asp.net core 一个中小型项目实战的起手式——项目搭建与仓储模式下的持久层创建(1)
- 值得花费一周研究的算法 -- KMP算法(indexOf)
- 重学计算机组成原理(五)- ";旋转跳跃";的指令实现
- Linux--shell编程原理--03
- springboot集成redis实现消息发布订阅模式-双通道(跨多服务器)