金陵十三钗(超简单DFS+剪枝）

解题思路:

记录一个最大值，如果当前搜索过程中的最大值 + 剩下层数 * maxv <= res  

则不可能更新最大值  ， 直接return
    故只需要加一句剪枝代码：

    if (s + (n - x + 1) * maxv <= res)

        return;

参考代码:

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <queue>

using namespace std;

typedef long long LL;

const int N = 15;

int g[N][N];

int n;

bool st[N];//第i列的人是否选择

int maxv;

int res;

void dfs(int x,int s)//第x行，总和为s

{

    if (x > n)

    {

        res = max(res,s);

        return;

    }

    if (s + (n - x + 1) * maxv <= res)

        return;

    for (int i = 1 ; i <= n ; i ++)

    {

        if (st[i]) continue;

        st[i] = 1;

        dfs(x + 1,s + g[x][i]);

        st[i] = 0;

    }

}

int main()

{

    cin >> n;

    for (int i = 1 ; i <= n ; i ++)

    for (int j = 1 ; j <= n ; j ++)

    {

        cin >> g[i][j];

        maxv = max(g[i][j],maxv);

    }

    dfs(1,0);

    cout << res << endl;

    return 0;   

}