大家一起做训练 第二场 E Cottage Village

题目来源：CodeForce #15 A

现在有 n 间正方形的房子，其中心点分布在 X轴 上，现在我需要新建一间边长为 t 的房子，要求新房子至少和一间房子相邻，但是不能和其他房子重合。请输出我有多少个位置可以选。

先分析一下：

　　因为现在要建一间边长为 t 的房子，而且要有一间房子与之相邻。所以，只有两种可能：第一种，在两端头。第二种，两间房子之间的间隔>= t。

分析完之后，做法已经是显而易见的了。首先，最少能建2间房子（在两端头）。然后就是遍历所有中心点，来计算房子间的距离，来判断能不能建房子。特别的，如果距离=t，只有一种方法。如果>t那么有两种。

时间效率：O( n * logn)，主要用在排序上。

附AC代码：

   1: #include <stdio.h>
   2: #include <iostream>
   3: #include <math.h>
   4: #include <stdlib.h>
   5: #include <string.h>
   6: #include <algorithm>
   7: #include <string>
   8: #include <vector>
   9: using namespace std;
  10:
  11: int t, n, pri[29], res[29], tmp[29], sum = 0;
  12:
  13: void dfs(int id)
  14: {
  15:     if (id > n)
  16:     {
  17:         int m = 0;
  18:         for (int i = 1; i <= n; i++)
  19:             if (tmp[i])
  20:                 m += pri[i];
  21:         if (m > sum && m <= t)
  22:         {
  23:             sum = m;
  24:             for (int i = 1; i <= n; i++)
  25:                 res[i] = tmp[i];
  26:         }
  27:         return;
  28:     }
  29:     else
  30:     {
  31:         tmp[id] = 1;
  32:         dp(id+1);
  33:         tmp[id] = 0;
  34:         dp(id+1);
  35:         return;
  36:     }
  37: }
  38:
  39: int main()
  40: {
  41:     while (~scanf("%d%d", &t, &n))
  42:     {
  43:         memset(res, 0, sizeof(res));
  44:         memset(tmp, 0, sizeof(tmp));
  45:         memset(pri, 0, sizeof(pri));
  46:         sum = 0;
  47:         for (int i = 1; i <= n; i++)
  48:             scanf("%d", &pri[i]);
  49:         dfs(1);
  50:         for (int i = 1; i <= n; i++)
  51:             if (res[i])
  52:                 printf("%d ", pri[i]);
  53:         printf("sum:%d\n", sum);
  54:     }
  55: }