列公子

## 完整代码 (AC)
```cpp
//
// 蓝桥杯题库 算法提高 1921 金陵十三钗
// 直接 DFS 时间超限
// DFS + 剪枝
//
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int G[maxn][maxn];  // 矩阵

int N, ans = 0;
bool vis[maxn];     // 该列是否已被选择
int maxV[maxn];     // 记录每一层及其下面所有层的最大收益 (最大值之和)

void dfs(int row, int total){       // 行, 已有的相似度之和
    if (row == N){
        ans = max(ans, total);
        return;
    }

for (int cc = 0; cc < N; cc++){     // 每一列
        if (!vis[cc] && maxV[row] + total > ans){
            vis[cc] = true;
            dfs(row + 1, total + G[row][cc]);
            vis[cc] = false;
        }
    }
}

int main(){
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%d", &G[i][j]);

for (int i = N-1; i > -1; i--){
        int now = 0;    // 本层的最大值
        for (int j = 0; j < N; j++){
            now = max(now, G[i][j]);
        }
        maxV[i] = maxV[i+1] + now;  // i层及以下所有层的最大收益
    }

dfs(0, 0);
    printf("%d", ans);
    return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言训练-最大数问题（C语言代码）.........关于-1

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

蓝桥杯金陵十三钗 DFS + 剪枝

评论区

精彩推荐

Cylinder （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

出圈】指针malloc版

蓝桥杯历届试题-翻硬币（C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

IP判断（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

陶陶摘苹果2 （C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

列公子