[12865] - LIS변형 DP활용

문제가 길어서 .... 문제를 짧게 설명하자면 책의 번호가 저렇게 정렬되어 있는데 순서대로 정렬을 할 때 최소의 노동력으로 정렬할 때 그때의 최소 노동력을 구하는 것이다.

이번 문제의 경우도 해매고, 해매고 ... 이 문제는 LIS알고리즘을 활용 한 것 이라는데 Longest increasing Subsequence 알고리즘으로 

이 문제의 포인트는 최소한의 노동력 = 전체값 - 그대로 두는 노동력의 최대값이라고 볼 수 있다는 것이다.

대략의 과정을 설명 하자면 앞에서 부터 시작을 한다.  813.8을 마지막으로 하는 정렬된 수열은 당연히 하나이므로 절약할 수 있는 노동력은 6이다.

그 다음 812의 경우에는 812보다 작은 수가 없으므로 6 혹은 자기 자신의 노동력 20 중 그대로 두는 노동력이 큰 20이 저장된다.

816의 경우에는 앞에 전부 자기보다 다 작은 수 이므로 6 혹은 20을 가져올 수 있고, 거기에 자기자신 5 을 더해서 25가 되는것이다.

813 은 812의 20 + 자기자신 8이다.

이렇게 모든 DP배열을 채우고 전체값 - dp배열의 최대값을 해주면 최소한의 노동력이 구해지는 것이다.

#include <stdio.h>

#include<iostream>

#include <algorithm>

using namespace std;

int main()

{

    int num;

    scanf("%d", &num);          //입력

    

    double n[5000];

    for(int i = 0; i < num; i++){

        scanf("%lf", &n[i]);

    }

    

    int f[5000];

    int sum = 0;

    for(int i = 0; i < num; i++) {

        scanf("%d", &f[i]);

        sum += f[i];                //총합

    }

    

    int dp[5000] = {0,};

    int maxs = 0;

    

    for(int i = 0; i < num; i++) {      //LIS알고리즘 부분

        for (int j = 0; j < i; j++){

            if(n[j] <= n[i]){

                dp[i] = max(dp[i], dp[j]);

            }

        }

        dp[i] += f[i];                  // 앞부분에서 최대값을 구하고 자기자신을 더해주는 과정(자기자신이 마지막인 수열이므로 자기자신은 안움직이므로)

        maxs = max(maxs, dp[i]);

    }

    

    printf("%d\n", sum - maxs);

    return 0;

}