题解 | #矩阵选数#
矩阵选数
https://ac.nowcoder.com/acm/contest/73810/D
https://ac.nowcoder.com/acm/contest/73810/D 状压dp法
#include<bits/stdc++.h>
using namespace std;
int dp[15][1 << 14];
int arr[15][15];
int main(void)
{
for (int i = 1; i <= 13; i++)
for (int j = 1; j <= 13; j++)
cin >> arr[i][j];
for (int i = 1; i <= 13; i++)
{
for (int j = 0; j < (1 << 13); j++)
{
for (int k = 0; k < 13; k++)
{
if (j & (1 << k))continue;
dp[i][j | (1 << k)] = max(dp[i][j | (1 << k)], dp[i - 1][j] + arr[i][k + 1]);
}
}
}
printf("%d", dp[13][(1 << 13) - 1]);
return 0;
}