2049042 2006-08-31 00:00:06 Accepted 1234 C++ 00:00.39 448K St.Crux 题意：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;}

评论