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

题目来源：CodeForce #15 A

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

先分析一下：

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

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

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

附AC代码：

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int t, n, pri[29], res[29], tmp[29], sum = 0;

void dfs(int id)
{
    if (id > n)
    {
        int m = 0;
        for (int i = 1; i <= n; i++)
            if (tmp[i])
                m += pri[i];
        if (m > sum && m <= t)
        {
            sum = m;
            for (int i = 1; i <= n; i++)
                res[i] = tmp[i];
        }
        return;
    }
    else
    {
        tmp[id] = 1;
        dp(id+1);
        tmp[id] = 0;
        dp(id+1);
        return;
    }
}

int main()
{
    while (~scanf("%d%d", &t, &n))
    {
        memset(res, 0, sizeof(res));
        memset(tmp, 0, sizeof(tmp));
        memset(pri, 0, sizeof(pri));
        sum = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d", &pri[i]);
        dfs(1);
        for (int i = 1; i <= n; i++)
            if (res[i])
                printf("%d ", pri[i]);
        printf("sum:%d
", sum);
    }
}