POJ3336 Making the Grade

아이디어: 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