HDU 5045 Contest

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

}

相关文章