练习题 - 我们的可可西里(动态规划)

前言

算法拾遗继续。

题目

问题描述

转眼到了2008年的6月9日,盼望已久的高考结束了。我们踏上了向西的旅程(本来是想写西去之路,可是考虑不太妥当)。可可西里,多么诱人的名词,充满了奇幻的色彩和自然的淳朴。从可可西里徒步走回家的决定是在1年半前定下的,而现在,终于可以实现那个钩过手指的预定。我们的可可西里。。。

在回家的路上,疯子和蚊子看到了许多可爱的藏羚羊,无意之中疯子和蚊子发现藏羚羊的居住地的分布也是有规律的,虽然疯子和蚊子早就听说藏羚羊是一种群体性很强又有超高IQ的动物,但是还是为它们的居住地分布规律感到惊叹。经过细心的观察,疯子和蚊子发现,如果假设一个藏羚羊群体有N只羊,就可以把它们的领地当做一个N*N的方阵,在这个方阵上第I列的第I行都有一个圣地,它们不会居住在圣地,同时每行每列只能居住一只羚羊。于是他们很快算出一个有N只羊的藏羚羊群体的居住地分布方法数。

这是圣地的一种排列方法

输入(keke.in)

一个整数N 代表藏羚羊的个数

输出(keke.out)

一个整数sum代表方法数

样例

keke.in

4

keke.out

9

数据规模

对于30%的数据,n<=10 对于全部数据 n<=1000

解答

本题最大的问题实际上并不是算法,更多的是数据结构。当n达到一定的数值时,羚羊的排列方式数量将远大于64位存储空间所能容纳的整数范围,因此需要采用数组的方式存储最后的结果。

解题方面,易知动态规划状态转移方程为

ans[i] = ans[i - 1] * (i - 1) + ans[i - 2] * (i - 1)

具体代码实现如下。

#include <stdio.h>
#include <string.h>

int n, len = 0;
int ans[4][10000] = {0};
int anslen[4] = {0};

void fdowork(int k, int x[], int y[], int ylen, int z[], int zlen) {
  int sum1[10000] = {0}, len1, sum2[10000] = {0}, len2;
  int i;
  for (i = 0; i < ylen; i++)
    sum1[i] = y[i] * (k - 1);
  for (i = 0; i < zlen; i++)
    sum2[i] = z[i] * (k - 1);
  int lenmax = ylen > zlen ? ylen : zlen;
  for (i = 0; i < lenmax; i++)
    x[i] = sum1[i] + sum2[i];
  for (i = 0; i < lenmax; i++) {
    x[i + 1] += x[i] / 10;
    x[i] %= 10;
  }
  while (x[lenmax] > 0) {
    x[lenmax + 1] += x[lenmax] / 10;
    x[lenmax] %= 10;
    lenmax++;
  }
  anslen[k % 4] = lenmax;
}

int main() {
  scanf("%d", &n);
  int i, j;
  if (n == 0)
    printf("0\n");
  else if (n == 1)
    printf("0\n");
  else if (n == 2)
    printf("1\n");
  else if (n == 3)
    printf("2\n");
  else {
    ans[2][0] = 1;
    anslen[2] = 1;
    ans[3][0] = 2;
    anslen[3] = 1;
    for (i = 4; i <= n; i++)
      fdowork(i, ans[i % 4], ans[(i - 1) % 4], anslen[(i - 1) % 4],
              ans[(i - 2) % 4], anslen[(i - 2) % 4]);

    for (i = anslen[n % 4] - 1; i >= 0; i--)
      printf("%1d", ans[n % 4][i]);

    printf("\n");
  }

  return 0;
}

后记

如果采用Python实现本题的话应该会显得非常简单,因为Python里面的Long integers have unlimited precision.

参考


* cached version, generated at 2018-12-02 17:48:40 UTC.

Subscribe by RSS