CF431B

dengruixun · 2023-08-01 17:58:04 · 题解

用深搜就可以了。

首先得循环输入矩阵。

for(int i = 1;i<=5;i++){
    for(int j = 1;j<=5;j++){
        cin>>a[i][j];
    }
}

注意 cur 判断时要等于 6 才能退出！！！

然后套公式：(a[s[1]][s[2]]+a[s[2]][s[1]]+a[s[3]][s[4]]+a[s[4]][s[3]])+(a[s[2]][s[3]]+a[s[3]][s[2]]+a[s[4]][s[5]]+a[s[5]][s[4]])+(a[s[3]][s[4]]+a[s[4]][s[3]])+(a[s[4]][s[5]]+a[s[5]][s[4]])

然后就没有然后了。

完整 CODE :

#include<bits/stdc++.h>
using namespace std;
int a[5+5][5+5];
int maxi = -1e9;
int s[6];
bool vis[6];
int ans;

void chek(){
    int k = (a[s[1]][s[2]]+a[s[2]][s[1]]+a[s[3]][s[4]]+a[s[4]][s[3]])
    +(a[s[2]][s[3]]+a[s[3]][s[2]]+a[s[4]][s[5]]+a[s[5]][s[4]])
    +(a[s[3]][s[4]]+a[s[4]][s[3]])
    +(a[s[4]][s[5]]+a[s[5]][s[4]]);
    maxi = max(maxi,k);
}

void dfs(int cur){
    if(cur==6){
        chek();
        return ;
    }
    for(int i = 1;i<=5;i++){
        if(vis[i]==false){
            vis[i] = true;
            s[cur] = i;
            dfs(cur+1);
            s[cur] = 0;
            vis[i] = false;
        }
    }
}

int main(){
    for(int i = 1;i<=5;i++){
        for(int j = 1;j<=5;j++){
            cin>>a[i][j];
        }
    }
    dfs(1);
    cout<<maxi;
    return 0;
}