[POJ 3666]Making the Grade[DP]

제목 링크: [POJ 3666] Making the Grade[DP] 문제 분석: n개의 수를 포함하는 서열로 서열의 임의의 수를 더하거나 줄일 수 있습니다. 질문: 최소한 몇 개의 값을 변경하여 원 서열을 단조롭게 증가하거나 단조롭게 줄일 수 있습니까?문제풀이 사고방식: 한 숫자의 수정에 대해 우리는 그것을 서열에 있는 숫자로 수정하는 것이 가장 좋은 선택이다(나는 반례를 찾지 못해서 이해한다==).그러면 우리는 먼저 이 숫자들을 복사해서 순서를 정할 수 있다. 다음은 상태 dp[i][j]를 i개수로 설정하고 b[j]를 마지막으로 변경하는 최소 가치이다.그러면 전이 방정식이 있어요.
dp[i][j]=min(dp[i−1][k])+|a[i]−b[j]|(k=0∼j)
이 방정식은 삼방식이어서 이 문제에 대해서는 분명히 T할 것이다.min(dp[i-1][k])이 전 j항의 최소값임을 알아차리면 이동할 때 이 최소값을 유지하면 됩니다.이렇게 하면 제곱의 복잡도를 낮출 수 있다.
개인적인 느낌:
전 n항의 화합, 최소치 등 모두 이렇게 최적화할 수 있다.
구체적인 코드는 다음과 같습니다.

#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#define ll long long
using namespace std;

const int INF = 0x7f7f7f7f;
const int MAXN = 2e3 + 111;

int a[MAXN], b[MAXN];
int dp[MAXN][MAXN];

bool cmp(int a, int b) {
    return a > b;
}

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i], b[i] = a[i];

    sort(b, b + n);
    for (int i = 0; i < n; ++i) dp[0][i] = abs(a[0] - b[i]);
    int ans1 = INF;
    for (int i = 1; i < n; ++i) {
        int pre = dp[i - 1][0];
        for (int j = 0; j < n; ++j) {
            pre = min(pre, dp[i - 1][j]);
            dp[i][j] = pre + abs(a[i] - b[j]);
        }
    }
    for (int i = 0; i < n; ++i) {
        ans1 = min(ans1, dp[n - 1][i]);
    }

    sort(b, b + n, cmp);
    for (int i = 0; i < n; ++i) dp[n - 1][i] = abs(a[n - 1] - b[i]);
    int ans2 = INF;
    for (int i = n - 2; i >= 0; --i) {
        int pre = dp[i + 1][n - 1];
        for (int j = n - 1; j >= 0; --j) {
            pre = min(pre, dp[i + 1][j]);
            dp[i][j] = pre + abs(a[i] - b[j]);
        }
    }
    for (int i = 0; i < n; ++i) {
        ans2 = min(ans2, dp[0][i]);
    }

    cout << min(ans1, ans2) << '
';
    return 0;
}