[PKU3666]Making the Grade [USACO 2008 Feb]

一个显然的事实:当b[]中的所有元素都出现在a[]中时,答案最小。

因此,不妨将a[]离散化到v[],先不考虑降序(因为数据中没有降序,所以我程序里面也就没有打降序),接下来就是一个水水的二维动规了:

f[i][j]表示前i个元素升序,并且把a[i]改成v[i]的最小代价。那么就有:

f[i][j] = min(f[i-1][k])+abs(a[i]-v[j]) (k<=j)

显然min(f[i-1][k])可以记录下来,因此复杂度只有O(nm)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <vector>
#include <algorithm>

int n, a[2001], f[2001][2001], g[2001][2001];
int main()
{
  scanf("%d", &n);
  std::vector<int> v;
  for (int i = 1; i <= n; ++i)
  {
    scanf("%d", a+i);
    v.push_back(a[i]);
  }
  std::sort(v.begin(), v.end());
  int m = std::unique(v.begin(), v.end()) - v.begin();

  for (int i = 1; i <= n; ++i)
  {
    g[i][0] = 0x7fffffff;
    for (int j = 1; j <= m; ++j)
    {
      f[i][j] = g[i-1][j]+std::abs(v[j-1]-a[i]);
      g[i][j] = std::min(g[i][j-1], f[i][j]);
    }
  }
  printf("%d", g[n][m]);
}

Comments