ACM模版

描述

题解

这个题说好的 dp 呢？我感觉怎么这道题不适合用 dp 啊？用 dp 写好麻烦的啊……

推导一下可以发现是一个数论题，当然，也可以使用搜索来暴解，毕竟蓝桥总是可以暴解。

首先我们通过画图可以发现，所有可行解的二维图像都类似于声呐波扩散的图，是一个扇形，这个不难发现，在选定的任意子集中，能够满足这样的要求的画法只有两种，所以我们只需要把所有满足题意的子集求出来乘以二就好了，这也就变成了求：

2∗(C(n,2)+C(n,3)+…+C(n,n))
（代码 One），这里需要解释一下，通过 C(n,m) 求出来的任意组合都是满足前三个条件的。

此时，我们可以想到高中学过一个不知道推论，暂且叫推论吧……

C(n,0)+C(n,1)+…+C(n,n)=2n
所以最前边的式子又可以变为
2∗(2n−n−1)
（代码 Two），这样一来，一行代码的事搞定。

代码

One：

#include <iostream>

using namespace std;

int com(int n, int r)
{
    if (n - r > r)
    {
        r = n - r;
    }
    int s = 1;
    for (int i = 0, j = 1; i < r; i++)
    {
        s *= (n - i);
        for (; j <= r && s % j == 0; j++)
        {
            s /= j;
        }
    }

    return s;
}

int main(int argc, const char * argv[])
{
    int k;
    cin >> k;

    int res = 0;
    for (int i = 2; i <= k; i++)
    {
        res += com(k, i);
    }

    cout << res * 2 << '\n';

    return 0;
}

Two：

#include <cstdio>
#include <cmath>

int main()
{
    int k;
    scanf("%d", &k);
    printf("%d\n", (int)(pow(2, k) - k - 1) * 2);

    return 0;
}