题目链接：http://lightoj.com/volume_showproblem.php?problem=1011
思路:最近的开始做dp了。。。很明显的一道状态压缩题，dp[n][state]表示前n行状态为state的最大值。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 int dp[17][1<<17]; 8 int n, num[17][17]; 9 10 int main() 11 { 12 int _case, t = 1; 13 scanf("%d", &_case); 14 while(_case--){ 15 scanf("%d", &n); 16 for(int i = 0; i < n; i++) 17 for(int j = 0; j < n; j++) 18 scanf("%d", &num[i][j]); 19 for(int i = 0; i < n; i++) 20 for(int j = 0; j < (1<<n); j++)dp[i][j] = -1; 21 for(int i = 0; i < n; i++)dp[0][1<<i] = num[0][i]; 22 for(int i = 1; i < n; i++){ 23 for(int state = 0; state < (1<<n); state++){ 24 for(int j = 0; j < n; j++)if(!(state&(1<<j))){ 25 if(dp[i-1][state] == -1)continue; 26 dp[i][state|(1<<j)] = max(dp[i][state|(1<<j)], dp[i-1][state]+num[i][j]); 27 } 28 } 29 } 30 printf("Case %d: %d ", t++, dp[n-1][(1<<n)-1]); 31 } 32 return 0; 33 } 34 35