最近偏爱这类题目。当然，这题的Accepted Submit也相当的多。对这类题，我的原则是，宁可错杀一万，不可放过一个。对于弱题天生的嗅觉。

    ......然而事物的现象和本质永远都是有差距的。这句话在哪里都适用。想算法用了10分钟，修改和提交用了整整1个钟头。题目如下。

    给定两个数N和M。比如4和10。求序列An的个数。序列An从某个正整数开始——比如1，每个数都要>=前一个数的2倍，最后一个数<=M，序列长度为N。

    但是我还是偷懒了。一般的讲，看到题目以后，尤其是长且欠的题目，我的第一反应一定是打开译题站，然后输入题号，搜索。这除了降低我的英语阅读能力和增强我对于网络的依赖性以外没有任何好处。然后我的第二反应就是看贴，不自觉，或者自觉的。接下来第三步，我看到了标准解法......幸好很多题目我还看的懂。今天我只瞄到了两个字：dp。

    ......OK，那么dp吧。

    其实就像fatboy大人讲过的，dp只是一种思路，并不是一种算法。当我们不把dp当成dp的时候，我们自然就会dp了。

    停。我不是杨过。我不会武功。还是讲讲思路吧。

    还是拿4，10做例子。

    这个例子里，我们能组成4个序列。

    1,2,4,8 

    1,2,4,9

    1,2,4,10

    1,2,5,10

    我的直觉告诉我，一定有递推关系。（......好吧，是帖子告诉我的）首先否决的是搜...搜索。N= 50, M= 2000，C(50,2000) = ∞，四核CPU都不够用。我很快想到了一点：

    如果用f(i, k)来表示答案。i表示序列的长度，k表示序列当前用到的最大数，也就是最后一个数的值。那么是不是容易递推呢？比如说这个例子。f(4, 10) = f(4, 9) + 9和10的差值 + f(3, 10 / 2)。因为5作为第三个数的时候，不存在9为第个数的情况。这是分成三部分。

    后来一想不对。一则9和10的差值难以计算。二来5作为第三个数的时候，也可能4是第三个数，和f(4,9)重负了。于是干脆把这个k改成当前序列的最后一个数。试了一下，果然方便多了。

    方程如下：f(i,k) = ∑f(i - 1, j) 这个j是比k / 2 小的所有数。

    还要注意一个恶心的地方：越界。所以用了double。

#include <cstdio>
#include <string>

int a, n, m;
double b[51][2001], r[51][2001]; 

int main()
{
 //freopen("in.txt", "r", stdin);
 scanf("%d", &a);
 int i, k, j;
 for(i = 0; i < a; i ++)
 {
  scanf("%d %d", &n, &m);
  memset(b, 0, sizeof(b));
  memset(r, 0, sizeof(r));
  for(j = 1; j <= m; j ++)
  {
   b[1][j] = 1;
  }
  double t = 0;
  for(j = 1; j <= m; j ++)
  {
   t += b[1][j];
   r[1][j] = t;
  }
  for(k = 2; k <= n; k ++)
  {
   t = r[k][1];
   for(j = 2; j <= m; j ++)
   {   
    b[k][j] = r[k - 1][j / 2];
    t += b[k][j];
    r[k][j] = t;
   }
  }
  //pb();
  //pr();
  printf("Case %d: n = %d, m = %d, # lists = %0.0f\n", i + 1, n, m, r[n][m]);
 }
 return 0;
}

 ----------------------------------------------------------------------

汗,题目已修改............谢谢匿名同学

评论