이 알고리즘의 정확성을 증명하는 방법은 무엇입니까?

Question

codeforces에서 문제를 해결하고 있습니다.

우리의 임무는 주어진 정수 시퀀스를 감소하지 않는 시퀀스로 만들기위한 최소 비용을 찾는 것입니다. 각 단계에서 시퀀스의 수를 1 씩 증가/감소시킬 수 있으며 1 씩 증가합니다.

예를 들어 시퀀스 3, 2, -1, 2, 11이 주어지면 시퀀스를 만들 수 있습니다 선정 된 4 감소 아닌 수 (2에 3 감소하고 2에 -1을 증가시켜, 따라서 비 감소 시퀀스 2, 2, 2, 2, 11이 될 것이다)이 문제의 editorial 따르면

우리 해결 이 문제는 2 시퀀스 (하나는 우리가 주어진 시퀀스이고 다른 하나는 주어진 시퀀스의 정렬 된 시퀀스)를 사용하여 동적 프로그래밍을 사용합니다.

용액의 개요 : 우리 a 원래 순서하고 b 시퀀스 a의 정렬 순서, 그리고 f(i,j)는 시퀀스를 획득하기 위해 요구되는 이동의 최소한의 수 있도록 해주면

되는 제의 i 요소는 감소하지 않고 i 번째 요소는 기껏해야 bj입니다. 그러면 다음과 같이 재발 할 수 있습니다. (이것은 문제의 사설에서 발췌 한 것입니다)

f(1,1)=|a1-b1| 
f(1,j)=min{|a1-bj|,f(1,j-1)}, j>1 
f(i,1)=|ai-b1|+f(i-1,1), i>1 
f(i,j)=min{f(i,j-1),f(i-1,j)+|ai-bj|}, i>1, j>1 

나는이 재발을 이해한다. 그러나 원래 시퀀스를 정렬 된 시퀀스와 비교해야하는 이유를 알 수 없으며 주어진 시퀀스의 정렬 된 시퀀스 이외의 다른 시퀀스를 사용하여 올바른 최소 비용을 얻을 수 있는지 여부를 확신 할 수 없습니다.

이 솔루션의 정확성을 어떻게 입증 할 수 있습니까? 그리고 정렬 된 순서로 답을 최저 비용으로 어떻게 보장 할 수 있습니까?

Answer 1

운동의 요점은이 재발이 유도와 함께 입증 될 수 있다는 것입니다. 일단 입증되면, f(n,n)은 n 값이 많아야 bn 인 솔루션으로 감기에 필요한 최소 비용입니다.

결과를 증명하는 작업을 완료하려면 한 단계 더 나아갑니다. 어느 것이 최대 값을 증가시키지 않고도 n 값이 bn을 초과하는 솔루션을 향상시킬 수 있음을 증명할 수 있습니다. 하지만 그건 사소한 일입니다. 첫 번째 값에서 +1의 값 중 하나를 생략하여 bn을 초과하면 더 큰 최대 값이없는 엄격한 해결책이됩니다. 따라서 최대 값이 bn보다 큰 최대 해법은 최대 값이 최대 값 인 bn보다 좋을 수 있습니다.

따라서 우리에게는 최적의 솔루션이 있습니다.