JNU 第四届 校赛 网络赛 D 迎接知名校友 【dfs+贪心】

D题

要求 n*n的方阵中 取n个数，保证每行每列各有一个，这样的取法有n!种，这里可以用 next_permutation求一个全排列就好了，但是由于里面有 若干个被涂抹的数，对于一种方案来说，如果要使得他最大，只可能填入大的数，所以，统计一下这种方案中 0 的个数，从大到小，填入m个数当中的数即可。复杂度是 o(n!)

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define sc(x) scanf("%d",&x)
using namespace std;
int a[105][105];
int pre[105];
int b[105];
int c[20];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    rep(i,1,n) rep(j,1,n) sc(a[i][j]);
    rep(i,1,m) {sc(b[i]);}
    sort(b+1,b+1+m,cmp);
    rep(i,1,m) pre[i]=pre[i-1]+b[i];
    rep(i,1,n) c[i]=i;
    long long ans=0;
    do
    {
        long long res=0;
        int cnt=0;
        rep(i,1,n) {res+=a[i][c[i]]; if(a[i][c[i]]==0)cnt++;}
        res += pre[cnt];
        ans = max(ans,res);
    }while(next_permutation(c+1,c+1+n));
    cout<<ans<<endl;

    return 0;
}