洛谷p1559运动员最佳匹配问题

//bao li
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 30;
int n, a[N][N], b[N][N], maxn[N], ans;
bool vis[N];
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == ‘-‘) w = -1; ch = getchar();}
    while(isdigit(ch)) {s = s * 10 + ch - ‘0‘; ch = getchar();}
    return s * w;
}
void dfs(int dep, int w) {
    if(dep > n) {ans = max(ans, w); return;} 
    int sum = 0;
    for(int i = dep; i <= n; i++) sum += maxn[i];
    if(w + sum < ans) return;
    for(int i = 1; i <= n; i++) 
        if(!vis[i]) {
            vis[i] = 1;
            dfs(dep + 1, w + a[dep][i] * b[i][dep]);
            vis[i] = 0;
        }
}
int main() {
    n = read();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            a[i][j] = read();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            b[i][j] = read();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            maxn[i] = max(maxn[i], a[i][j] * b[j][i]);
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}