题目链接：https://nanti.jisuanke.com/t/31436
作为一名车手，为了提高自身的姿势水平，平时的练习是必不可少的。小 J 每天的训练包含 $N$ 个训练项目，他会按照某个顺序依次练习这些项目。出于一些玄妙的原因，训练的效果跟项目的顺序有着很大关系。当项目 $i$ 被安排在项目 $j$ 之前进行训练，小 J 会获得 $a_{i,j}$ 的熟练度，否则他会获得 $a_{j,i}$ 的熟练度。为了使训练效果尽可能好，小 J 希望这 $\frac{N(N-1)}2$ 对项目的熟练度之和达到最大。请你帮助小 J 确定训练的顺序，使得他获得的总熟练度尽可能大。
输入格式
输入第一行包含一个正整数 $N$。接下来 $N$ 行每行包含 $N$ 个整数，其中第 $i+1$ 行的第 $j$ 个数表示 $a_{i,j}$，保证 $a_{i,i}=0$
输出格式
输出一个整数表示最大总熟练度。
数据规模
对于 40% 的数据：$N \leq 8$；
对于 70% 的数据：$N \leq 15$；
对于 100% 的数据：$N\leq 20,0\leq a_{i,j} \leq 10000$；
输出时每行末尾的多余空格，不影响答案正确性
要求使用「文件输入输出」的方式解题，输入文件为 proficiency.in，输出文件为 proficiency.out
样例输入
3
0 2 4
3 0 2
1 3 0
样例输出
9
题目来源
计蒜客 NOIP 提高组模拟竞赛第一试
题解：
状压DP水题。
时间复杂度 $O(2^N N^2)$
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=; int n,a[maxn][maxn];
int dp[<<maxn];
int main()
{
freopen("proficiency.in","r",stdin);
freopen("proficiency.out","w",stdout); cin>>n;
for(int i=;i<=n;i++) for(int j=;j<=n;j++) cin>>a[i][j]; memset(dp,,sizeof(dp));
for(int sta=;sta<(<<n);sta++)
{
for(int i=;i<=n;i++)
{
if(sta&(<<(i-))) continue;
int nxt=sta|(<<(i-));
int sum=;
for(int j=;j<=n;j++) if(sta&(<<(j-))) sum+=a[j][i];
dp[nxt]=max(dp[nxt],dp[sta]+sum);
}
}
cout<<dp[(<<n)-]<<endl;
}