主题链接~~>
做题感悟：比赛时这题后来才写的，有点小尴尬。两个人商议着写写了非常久才写出来，I want to Powerful ,I believe me .
解题思路：
遗憾 ！
感觉领悟能力太低 。由于随意时刻随意两个人做的题不超过 1 题 ，so~> 必须是一轮一轮的来（n 道题一轮），每一个人在一轮中仅仅能做一题。假设多做一题就，有可能某个人没选，某个人选择了两道，这样就不符合规定了 。 用 1 代表选择。0 代表没选择。进行某一行的时候就选择上一行某位为 0 的状态 。假设选择某位为 1的状态那么那个人就比某些人多选择了两门课程。
比赛时分轮来的，一轮一轮的来。最后有可能剩余零头。每次进行 n * n 的DP 。零头单独处理 ，每行每列选一个 。赛后看了大牛的解题报告顿时感觉太弱了。事实上能够等到选满的时候然后转移一下。转移到当前行的 0 状态，这样就能够继续从上一行的 0 状态往下 dp 。
代码：
#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define INT __int64
const double INF = 99999999 ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const int MY = 100000 + 5 ;
const int MX = 1024 + 5 ;
int n ,m ;
double dp[MX][MX] ,mp[MX][MX] ;
int main()
{int Tx ,cse = 1 ;cin>>Tx ;while(Tx--){cin>>n>>m ;for(int i = 0 ;i < n ; ++i)for(int j = 0 ;j < m ; ++j)cin>>mp[j][i] ;for(int i = 0 ;i < m ; ++i)for(int j = 0 ;j < (1<<n) ; ++j)dp[i][j] = -1.0 ;for(int i = 0 ;i < n ; ++i)dp[0][1<<i] = mp[0][i] ;for(int i = 1 ;i < m ; ++i)for(int j = 0 ;j < (1<<n) ; ++j)for(int k = 0 ;k < n ; ++k){if(dp[i-1][j] < 0 || (j&(1<<k))) continue ;if((j|(1<<k)) != (1<<n)-1) // 推断是否选满dp[i][j|(1<<k)] = max(dp[i][j|(1<<k)] ,dp[i-1][j] + mp[i][k]) ;else dp[i][0] = max(dp[i][0] ,dp[i-1][j] + mp[i][k]) ;}double ans = 0 ;for(int i = 0 ;i < (1<<n) ; ++i)ans = max(ans ,dp[m-1][i]) ;cout<<"Case #"<<cse++<<": "<<fixed<<setprecision(5)<<ans<<endl ;}return 0 ;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
