题意：3个数一套，(a1≤a2≤a3)，并定义c =(a1 - a2)^2 。在M个已排序数里找出N套这样的数，使得∑c最小。

典型的组合式dp题。这题的关卡在于：数是一套的，而不是一个，而第三个数又是无用的。但是有一点：a1和a2必然是临近的数，(不然必大于这种最优选择)即取到第k个数时，对于ak和ak-1只有两种选择：

1.不取。2.取。(........) 捆绑考虑。

和所有的组合dp一样，可以列出方程：

opt[i, k] = opt[i - 1, k - 2] + (ak - ak-1)^2  (1≤i≤n, 1≤k≤m)

且opt[i, k] = opt[i, k - 1]

其中opt表示前k个数里取i个能取到的最小值。其中k对于每个i都有取值范围，两边都有，这个和组合dp一样，只不过稍显复杂一些。

而这显然要优化，数组开这么大，1000×5000，还好现在内存便宜。但是还得优化，n值一大照样破产。

那么，只需要两个数组便可。这个也是老规矩了，上一步的先存在b[0]里，每个做完了放b[1]里，等k循环完一遍就可把b[1]赋值给b[0]。这是一种经常用的手法，也是所有不写注释的程序最让人百思不得其解的地方。

#include <cstdio>
#include <string>

#define MX 99999999

int a[5001], b[2][5001], c, n, m;

void init()
{
 memset(b, 0, sizeof(b));
}

void dp()
{
 int i, k;
 for(i = 1; i <= m; i ++)
 {
  for(k = 2 * i; k <= n; k ++)
  {
   b[1][k] = MX;
   if(k > 2 * i) b[1][k] = b[1][k - 1];
   if(n - k > (m - i) * 3)
   {
    int t = b[0][k - 2] + (a[k] - a[k - 1]) * (a[k] - a[k - 1]);
    if(t < b[1][k]) b[1][k] = t;
   }
  }
  memcpy(b[0], b[1], sizeof(b[1]));
 }
}

void prt()
{
 //pt();
 printf("%d\n", b[1][n]);
}

 
int main()
{
 //freopen("in.txt", "r", stdin);
 scanf("%d", &c);
 int i, k;
 for(i = 0; i < c; i ++)
 {
  scanf("%d %d", &m, &n);
  m += 8;
  for(k = 1; k <= n; k ++)
  {
   scanf("%d", &a[k]);
  }
  init();
  dp();
  prt();
 }
 return 0;
}

评论