POJ3336 Making the Grade
1646 단어 데이터 구조와 알고리즘
아이디어: DP
제출: 1회
문제 풀이:
처음에 우리는 두 가지 서열로 나누어 모두 한 번 해 보라고 생각할 수 있었다.먼저 결론을 증명합니다.\(B\) 의 수가\(A\) 에 나타났고, 이렇게 하면 나쁘지 않습니다.(일시적으로 허무맹랑해 보이는 DP를 전환하기 위해서) 분명히 하나의 수가 성립되었음을 고려하여\(B\)의 앞\(k-1\)항목을 고려하고 뒤에 하나의 수\(B k\)를 삽입합니다.만약\(B {k-1}\leq A k\)가 있다면 우리는 직접 점차적으로 삽입할 것이다. 그렇지 않으면\(B k=B {k-1}\) 또는\(j\)가 존재하여\(B j, B {j+1},\cdots, B {k}\)가 같고 대가가 더 적다(중위수의 성질).이렇게 해서 우리는 DP:\(f[i][j]\) 앞\(i\) 개수를 고려하고 마지막 개수는\(j\)(주의\(j\)는 이산화 후의 위치)\(f[i][j]=\min {0\leq k\leq j}(f[i-1][k]+|j-A i|)\)는 하나의\(i\) 결정 집합이 단조롭게 확대되고 있음을 알아차렸기 때문에 하나의 변수로 앞의 최소값을 기록하고 직접 이동할 수 있다.
코드:
#include
#include
#include
#include
#define R register int
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;
} const int N=2010;
int n,m,a[N],b[N];
int f[N][N],ans=1e+9;
inline void main() {
n=g(); for(R i=1;i<=n;++i) b[i]=a[i]=g();
sort(b+1,b+n+1); R m=unique(b+1,b+n+1)-b-1;
memset(f,0x3f,sizeof f); f[0][0]=0;
for(R i=1;i<=n;++i) {
R mn=f[i-1][0];
for(R j=1;j<=m;++j) {
mn=min(mn,f[i-1][j]);
f[i][j]=mn+abs(a[i]-b[j]);
}
} for(R i=1;i<=m;++i) ans=min(ans,f[n][i]);
printf("%d
",ans);
}
} signed main() {Luitaryi::main(); return 0;}
2019.09.18 58
전재 대상:https://www.cnblogs.com/Jackpei/p/11545585.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.