POJ. 3666 Making the Grade

1.Problem
http://poj.org/problem?id=3666

2.Idea
See this.

3.Source

 ll a[2003];  
 ll h[2003];  
 int n;  
 ll dp[2003][2003];  
 ll Min(ll a, ll b)  
 {  
      if (a > b) return b;  
      else return a;  
 }  
 ll solve()  
 {  
      for(int i=0;i<2003;i++)  
           for (int j = 0; j < 2003; j++) {  
                dp[i][j] = 1 << 30;  
           }  
      dp[0][0] = 0;  
      for (int i = 0; i < 2003; i++) {  
           ll minCost = 1 << 30;  
           for (int j = 0; j < 2003; j++) {  
                minCost = Min(minCost, dp[i][j]);  
                dp[i + 1][j] = minCost + abs((long)a[i] - (long)h[j]);  
           }  
      }  
      ll ans = 1 << 30;  
      for (int i = 0; i < n; i++) {  
           ans = Min(ans, dp[n][i]);  
      }  
      return ans;       
 }  
 int main()  
 {  
      ll ret = (1 << 30);  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           cin >> a[i];  
           h[i] = a[i];  
      }  
      //asc  
      sort(h, h + n);  
      ret = Min(ret, solve());  
      //desc  
      reverse(a, a + n);  
      sort(h, h + n);  
      ret = Min(ret, solve());  
      cout << ret << endl;  
      return 0;  
 }