C - Sonya and Problem Wihtout a Legend
思路:感觉没有做过这种套路题完全不会啊。。 把严格单调递增转换成非严格单调递增,所有可能出现的数字就变成了原数组出现过的数字。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define PLI pair<LL, int>
#define ull unsigned long long
using namespace std; const int N = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ; LL dp[N][N], a[N], hs[N], tot, n; int main() {
memset(dp, INF, sizeof(dp));
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%lld", &a[i]);
a[i] = a[i] - i;
hs[tot++] = a[i];
}
sort(hs, hs + tot);
tot = unique(hs, hs + tot) - hs; for(int j = ; j < tot; j++) dp[][j] = abs(a[] - hs[j]); for(int i = ; i <= n; i++) {
LL mn = INF;
for(int j = ; j < tot; j++) {
mn = min(mn, dp[i - ][j]);
dp[i][j] = min(dp[i][j], mn + abs(a[i] - hs[j]));
}
}
LL ans = INF;
for(int j = ; j < tot; j++)
ans = min(ans, dp[n][j]);
printf("%lld\n", ans);
return ;
} /*
*/
Codeforces Round #371 (Div. 1) C - Sonya and Problem Wihtout a Legend的更多相关文章
-
Codeforces Round #371 (Div. 1) C. Sonya and Problem Wihtout a Legend 贪心
C. Sonya and Problem Wihtout a Legend 题目连接: http://codeforces.com/contest/713/problem/C Description ...
-
Codeforces Round #371 (Div. 2)E. Sonya and Problem Wihtout a Legend[DP 离散化 LIS相关]
E. Sonya and Problem Wihtout a Legend time limit per test 5 seconds memory limit per test 256 megaby ...
-
Codeforces Round #371 (Div. 2) C. Sonya and Queries 水题
C. Sonya and Queries 题目连接: http://codeforces.com/contest/714/problem/C Description Today Sonya learn ...
-
Codeforces Round #371 (Div. 2) C. Sonya and Queries —— 二进制压缩
题目链接:http://codeforces.com/contest/714/problem/C C. Sonya and Queries time limit per test 1 second m ...
-
Codeforces Round #371 (Div. 2) C. Sonya and Queries[Map|二进制]
C. Sonya and Queries time limit per test 1 second memory limit per test 256 megabytes input standard ...
-
Codeforces Round #371 (Div. 2) C. Sonya and Queries
题目链接 分析:01trie树,很容易就看出来了,也没什么好说的.WA了一发是因为没有看见如果数字位数大于01序列的时候01序列也要补全0.我没有晚上爬起来打,白天发现过的人极多. /******** ...
-
Codeforces Round #371 (Div. 1)
A: 题目大意: 在一个multiset中要求支持3种操作: 1.增加一个数 2.删去一个数 3.给出一个01序列,问multiset中有多少这样的数,把它的十进制表示中的奇数改成1,偶数改成0后和给 ...
-
codeforces 713C C. Sonya and Problem Wihtout a Legend(dp)
题目链接: C. Sonya and Problem Wihtout a Legend time limit per test 5 seconds memory limit per test 256 ...
-
【CodeForces】713 C. Sonya and Problem Wihtout a Legend
[题目]C. Sonya and Problem Wihtout a Legend [题意]给定n个数字,每次操作可以对一个数字±1,求最少操作次数使数列递增.n<=10^5. [算法]动态规划 ...
随机推荐
-
安卓学习----使用okHttp(POST方式)---登录
工具类 package com.liunan.okhttpdemo3post.Utils; import java.io.IOException; import okhttp3.MediaType; ...
-
window.onload()和$(function(){});的区别
1.window.onload必须等到页面中所有元素加载完之后才会执行(包括图片.视频等)而$(function(){});是在结构绘制完毕之后执行,二者的执行时机是不同的,一般来说后者会首先执行 2 ...
-
【poj1740】 A New Stone Game
http://poj.org/problem?id=1740 (题目链接) 男人八题之一 题意 对于n堆石子,每堆若干个,两人轮流操作,每次操作分两步,第一步从某堆中去掉至少一个,第二步(可省略)把该 ...
-
Quartz作业调度框架
Quartz 是一个开源的作业调度框架,它完全由 Java 写成,并设计用于 J2SE 和 J2EE 应用中.它提供了巨大的灵活性而不牺牲简单性.你能够用它来为执行一个作业而创建简单的或复杂的调度.本 ...
-
Asp.net页面跳转Session丢失问题
原本去年在做项目时,写好的一记篇博客分享给大家. Asp.net页面跳转Session丢失问题 编写人:CC阿爸 2014-4-2 l 近来在做泛微OA与公司自行开发的系统集成登录的问题.在使用 ...
-
Unity3D之游戏暂停制作方法记录
在游戏开发中我们一般都需要涉及到一个功能:游戏暂停,但是这里指的暂停仅仅是核心模块的暂停,并不是整个游戏都暂停,比如一些UI和UI上的动画与特效是不能被暂停的,整个游戏都暂停了玩家该如何继续游戏呢. ...
-
GestureDetector和SimpleOnGestureListener的使用教程
1. 当用户触摸屏幕的时候,会产生许多手势,例如down,up,scroll,filing等等,我们知道View类有个View.OnTouchListener内部接口,通过重写他的onTouch(Vi ...
-
调试 JavaScript 脚本
随着 JavaScript 应用的复杂性逐渐提高,开发者需要有力的调试工具来帮助他们快速发现问题的原因,并且能高效地修复它.Chrome DevTools 提供了一系列实用的工具使得调试 JavaSc ...
-
JavaScript “类”定义 继承 闭包 封装
一.Javascript “类”: 类:在面向对象编程中,类(class)是对象(object)的模板,定义了同一组对象(又称"实例")共有的属性和方法. Javascript是一 ...
-
linux rpm安装 failed depenencie(失败的依赖关系)错误原因
rpm安装nfs 出现failed depenencie 经查资料得知命令后加上--nodeps --force,就可以了 加上那两个参数的意义就在于,安装时不再分析包之间的依赖关系而直接安装,也就不 ...