做题感悟:比赛时这题后来才写的,有点小尴尬。两个人商议着写写了非常久才写出来,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 ;
}

               

版权声明:本文博客原创文章,博客,未经同意,不得转载。

05-11 22:19