POJ 3666 Making the Grade(DP)

1876 단어 dppojACM-ICPC
제목 링크: 클릭하여 링크 열기
제목: n개의 수를 주고 이 수열을 비감소 또는 비증가 수열로 바꾸어 최소한의 변수의 합을 구하도록 요구한다.
사고방식: 이렇게 DP를 설계할 수 있다. d[i][j]는 i개수가 j로 변하는 가장 좋은 결과를 나타낸다. 이렇게 하면 d[i-1][k]로 옮길 수 있다. 그 중에서 k<=j는 상승하는 것이고 대가는 abs(a[i]-j)이다.그러나 수가 너무 많고 매 수가 반드시 이 수 중의 한 수가 될 것이기 때문에 우리는 n개의 수를 먼저 이산화시켜도 무방하다. 이런 상태는 d[i][j]로 표시하고 i개의 수가 j의 작은 수로 변하며 d[i-1][k]로 옮긴다. 그 중에서 k<=j이다.그러나 이렇게 하면 시간이 초과된다. 삼중순환이기 때문에 매번 전 층의 현재 최소치를 취하기 때문에 3층을 최적화하기 쉽다.
자세한 참고 코드:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const ll INF = (ll)2000000000000;
const int maxn = 2000 + 10;
int T,n,m,a[maxn],b[maxn],vis[maxn][maxn],kase=0;
ll d[maxn][maxn];
int main() {
    while(~scanf("%d",&n)) {
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            b[i] = a[i];
        }
        sort(b + 1, b + n + 1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) d[i][j] = INF;
        for(int i=1;i<=n;i++) d[1][i] = abs(a[1] - b[i]);
        ll ans = INF;
        for(int i=2;i<=n;i++) {
            ll last = INF;
            for(int j=1;j<=n;j++) {
                last = min(last, d[i-1][j]);
                d[i][j] = min(d[i][j], last + abs(a[i] - b[j]));
                if(i == n) ans = min(ans, d[i][j]);
            }
        }
        printf("%I64d
",ans); } return 0; }

좋은 웹페이지 즐겨찾기