POJ 3666 Making the Grade DP+離散化+欲張り

http://poj.org/problem?id=3666
題意:シーケンスを与えて、1つの数に1つの数を偽減することができて、代価は彼らが変えた数の絶対値で、それでは最小の代価でシーケンスを単調で非増加あるいは単調で非減少に変えることを要求します(ps本題のデータは非減少になるだけで済むようです)
n<=1e3
考え方はdp
dp[i][j]は、前のi個の数がjで終わる非減算シーケンスの最小代価を表し、もちろんこのjは離散化される 
dp[i]][j]=abs(a[i]-j)+dp[i-1][k](k<=j):すなわちi-1シーケンスの最適スキームから1つの遷移を選択する
i j kの3サイクルのように見えます
しかし、kがk<=jを満たすことは明らかである.すなわち、dp[i][j]を計算する場合、dp[i-1][1...j]の最小値を知る必要がある.
dp[i-1][1...j]は、dp[i][1...j-1]を計算する前にアクセスしたことがあるに違いありません.では、最小値mnを記録してみましょう.
dp[i]][j]=abs(a[i]-j)+mn
複雑度n*jの範囲
では、このjを見て、何を選ぶべきかを見てみましょう.明らかに、jが元のシーケンスを選択する数が一番いいです.c[i]を選択して最適値を得ると、最終的なシーケンスの費用が変わらず、すべて元のシーケンスの数を使うことができるからです.(欲張り)
従ってiは1−n,jはa[1..n]の列挙である.
複雑度n^2

using namespace std;  
const int N=2005;  
const long long inf=(1<<60);  
int n;  
int a[N],b[N];  
long long int dp[N][N];  
void solve()  
{  
    for(int i=1;i<=n;i++)  
    {  
        long long mn=dp[i-1][1];  
        for(int j=1;j<=n;j++)  
        {  
            mn=min(mn,dp[i-1][j]);  
            dp[i][j]=Abs(a[i]-b[j])+mn;  
        }  
    }  
    long long ans=dp[n][1];  
    for(int i=1;i<=n;i++)  
        ans=min(ans,dp[n][i]);  
    printf("%lld
",ans);  
}  
int main()  
{  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++)  
    {  
        scanf("%d",a+i);  
        b[i]=a[i];  
    }  
    sort(b+1,b+n+1);  
    solve();  
      
    return 0;  
}