状压dp

题目类型：状压dp
题目见链接
https://ac.nowcoder.com/acm/contest/283/F

#include<bits/stdc++.h>#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define m(a,b) make_pair(a,b)
const ll mod=1e9+7,mod2=998244353;
ull base=131;
const int w=1e7+5;
ll m,n;
ll dp[1<<15];
ll a[110][110];
int main()
{
    ll i,j,k,t;
    cin>>t;
    while(t--)
    {
        scanf("%lld",&n);
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                scanf("%lld",&a[i][j]);
        memset(dp,0,sizeof(dp));
        for(i=1;i<(1<<n);i++)     //从1开始，因为全为0，无意义
        {
            int tot=0;
            for(j=0;j<n;j++)
                tot+=(i>>j)&1;     //当前状况选择了的个数
            tot--;                //减掉一个进行转移
            for(j=0;j<n;j++)
                if((i>>j)&1)
                    dp[i]=max(dp[i],dp[i^(1<<j)]+a[tot][j]);
        }
        printf("%lld\n",dp[(1<<n)-1]);
    }
    return 0;
}