[USACO08FEB] 길 닦기 메이킹 더 그레이드.

제목 전송문:https://www.luogu.org/problem/P2893
이 학과의 신기한 dp.데이터의 Ai가 너무 커서 정렬 처리를 하고 그 아래를 크기로 표시합니다.
우리는 f[i][j]로 전 i단을 내리지 않는 서열로 바꾸었고 제j단 도로의 높이가 b[j]일 때의 최소 비용은 명백히 알 수 있다.
dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j]); (주:b[j]는 이산화 후 j번째 크기)

 1 #include
 2 using namespace std;
 3 int n;
 4 int ans=0x3f3f3f3f;
 5 int a[2009];
 6 int b[2009];
 7 int dp[2009][2009];//dp[i][j]
 8 inline long long read()
 9 {
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
13     return x*f;
14 }
15 bool cmp(int a,int b)
16 {
17     return a>b;
18 }
19 int main()
20 {
21     n=read();
22     for(int i=1;i<=n;i++)
23         a[i]=b[i]=read();
24     for(int i=1;i<=n;i++)dp[i][0]=0x3f3f3f3f;
25     sort(b+1,b+1+n);
26     for(int i=1;i<=n;i++)
27     {
28         for(int j=1;j<=n;j++)
29         {
30             dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j]));
31         }
32     }
33     ans=dp[n][n];
34     sort(b+1,b+1+n,cmp);
35     for(int i=1;i<=n;i++)
36     {
37         for(int j=1;j<=n;j++)
38         {
39             dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j]));
40         }
41     }
42     ans=min(ans,dp[n][n]);
43     cout<<ans;
44 }