[codeforces 13 C] [DP + 이산 화 + 욕심 + 스크롤 배열] C. Sequence [최소 대가 로 서열 을 비 엄격 한 증가 서열 로 바 꿉 니 다]
2776 단어 onlinejudgeCodeforces욕심
설명:
C. Sequence
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output
Little Petya likes to play very much. And most of all he likes to play the following game:
He is given a sequence of N integer numbers. At each step it is allowed to increase the value of any number by 1 or to decrease it by 1. The goal of the game is to make the sequence non-decreasing with the smallest number of steps. Petya is not good at math, so he asks for your help.
The sequence a is called non-decreasing if a1 ≤ a2 ≤ ... ≤ aN holds, where N is the length of the sequence.
Input
The first line of the input contains single integer N (1 ≤ N ≤ 5000) — the length of the initial sequence. The following N lines contain one integer each — elements of the sequence. These numbers do not exceed 109 by absolute value.
Output
Output one integer — minimum number of steps required to achieve the goal.
Examples
input
5
3 2 -1 2 11
output
4
input
5
2 1 1 1 1
output
1
제목:
n 개의 수 를 드 리 겠 습 니 다. 매번 조작 할 때마다 특정한 수 를 1 을 추가 하거나 1 을 줄 일 수 있 습 니 다. 적어도 몇 번 의 조작 을 통 해 이 n 개의 수 를 비 체감 시 킬 수 있 습 니 다.비점 감 정의: a1 ≤ a2 ≤ ... ≤ aN
생각:
이 문 제 는 대원제 이다
원 제 는 POJ 3666 입 니 다. 해제
그러나 이 카드 공간 은 스크롤 배열 을 최적화 시 켜 야 합 니 다. 초 지나(:зゝ∠)_
CF 714 E 해제
CF 가 원래 의 문 제 를 고 치 는 것 은 정말 즐 겁 지 않다. 그래도 문 제 를 많이 풀 어야 한다.
코드:
#include
#include
#include
#define ll __int64
using namespace std;
const int N=5005;
int n,a[N],b[N];
ll dp[2][N];
template void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH'9';F= CH=='-',CH=getchar());
for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
F && (num=-num);
}
void solve(){
for(int i=1; i<=n; i++){
ll mn=dp[(i-1)&1][1];
for(int j=1; j<=n; j++){
mn=min(mn, dp[(i-1)&1][j]);
dp[i&1][j]=abs(a[i]-b[j])+mn;
}
}
ll ans=dp[n&1][1];
for(int i=2; i<=n; i++){
ans=min(ans, dp[n&1][i]);
}
printf("%I64d
",ans);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
read(n);
for(int i=1; i<=n; i++){
read(a[i]);
b[i]=a[i];
}
sort(b+1, b+n+1);
solve();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
AZ-900을 자택 수험으로 무료 취득한 이야기 (2020/10)에서 2일간(오전중에만)의 온라인 트레이닝을 받는 것으로 무료 바우처를 받을 수 있다(등록 메일에 온다) 때문에, 부터 Peason VUE でスケジュール 버튼을 눌러, 화면에 따라 예약해 합격합시다 . ※2020/1...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.