CodeForces 13C Sequence (DP)
1852 단어 dpcodeforces
제목의 의미
n (1 < = n < = 5000) 개수의 서열을 제시합니다. 이 서열을 비체감으로 바꾸는 조작수는 최소한 얼마입니까?
매 조작은 n개 수 중의 어느 하나를 더하거나 줄일 수 있다
예를 들어 세 개의 수를 제시한다. 3, 2, 3. ->가장 좋은 방안은 두 번째 수를 1로 더하는 것이다. ->, 3, 3의 최소 조작수는 1이다.
문제풀이 방법
dp[i][j]-> 이전 i 개수가 j를 끝으로 하는 합법적인 서열로 변하는 데 필요한 최소 조작수
상태 이동 dp[i][j]=min(dp[i][j], dp[i-1][k]+코스트(원래 i번째 위치의 수가 j로 전환)(1<=k<=j)
즉, 전 i개수 j를 끝으로 (전 i-1개수가 j보다 작은 수로 끝난다)에서 옮길 수 있는데, 이때는 원래의 i개수에서 k로 옮기는 소모를 더해야 한다.
주의
입력한 수의 절대값은 1e9보다 작기 때문에 입력한 수를 이산화시켜야 하며, 점차적으로 추진할 때 스크롤 그룹으로 메모리를 최적화하여 MLE를 피할 수 있다
그리고 우리가 이동할 때마다 필요한 값이 j보다 작은 수의 최대 값이기 때문에 하나의 변수로 이 값을 저장하고 점차적으로 업데이트할 수 있습니다. 그렇지 않으면 TLE가
부록:
스탬프 -> 이산화란 무엇인가
학습 스크롤 배열
코드 참고. - 궁금한 거 있으면 댓글로 남겨주시면 빨리 답장해드릴게요.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 5000 + 10;
const LL INF = 1LL<<62;
LL a[MAXN], b[MAXN];
LL dp[2][MAXN];
int main() {
int n;
while(cin>>n) {
for( int i=0; i<n; i++ ) {
cin>>a[i];
b[i] = a[i];
}
sort(b, b + n);
int tn = unique(b, b + n) - b; // n
for( int i=0; i<tn; i++ ) dp[0][i] = abs(b[i] - a[0]), dp[1][i] = INF;
int now = 0;
for( int i=1; i<n; i++ ) {
LL t_min = INF;
for( int j=0; j<tn; j++ ) {
t_min = min(t_min, dp[now][j]);
dp[now^1][j] = min(dp[now^1][j], t_min + abs(b[j] - a[i]));
}
now ^= 1;
for( int j=0; j<tn; j++ ) dp[now^1][j] = INF;
}
LL n_min = INF;
for( int i=0; i<tn; i++ ) n_min = min(n_min, dp[now][i]);
cout<<n_min<<endl;
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
