乱八七糟的代码

roblem Statement

Character j in element i (both 0-based) of messages denotes how many messages employee i sent to employee j. You will return a vector <int> containing the hierarchy of the employees within the company. Element 0 is the highest ranked employee, and so forth. The returned ranking should minimize the number of messages sent from lower ranked employees to higher ranked employees. If multiple solutions are possible, return the one with element 0 minimal. If there are still ties, minimize element 1, etc.

Definition

Class:
CompanyMessages

Method:
getRank

Parameters:
vector <string>

Returns:
vector <int>

Method signature:
vector <int> getRank(vector <string> messages)

(be sure your method is public)

Constraints

-
messages will contain between 2 and 15 elements inclusive.

-
Each element of messages will contain exactly N characters, where N is the number of elements in messages.

-
Each character in messages will be a digit ('0'-'9').

-
Character i in element i of messages will be '0'.

按照题目说明可知，按照找到的顺序，所有从低级向高级发的信得数目和应该是最小的。又观察到，只要确定了第一个，也就是级别最高的boss，那么剩下的员工怎么排列，他们向最高boss 发信数是不变的，从而子问题就是在剩下员工中找到 低级向高级发信数最小的排列 ，显然这符合DP问题最优子结构的问题。

T[1···N]=Min{sum(N <->{1-N-1},T[1-N-1] } 得到状态方程后很容易写出程序 ，可以使用备忘录dp

Code Snippet

#define REP(i, n) for (int i = 0; i < (n); ++i)

#define two(X) (1<<(X))
#define contain(S,X) ((S&two(X))>0)

int A[1<<15];
vector<vector<int> > vec(1<<15);
class CompanyMessages
{
        public:
        vector <int> getRank(vector <string> mes )
        {
            int n=mes.size();
            REP(mask,two(n)){
                if(!mask)continue;
                A[mask]=100000;
                REP(i,n)if(contain(mask,i)){
                    int now=mask^two(i); int tmp=A[now];
                    REP(j,n)if(contain(now,j))tmp+=(mes[j][i]-'0');
                    if(tmp<A[mask]){
                        vec[mask].clear();vec[mask].push_back(i);
                        for(int s=0;s<vec[now].size();s++)vec[mask].push_back(vec[now][s]);
                        A[mask]=tmp;
                    }
                }
            }
            return vec[two(n)-1];
        }

 

Code Snippet

int memo[two(15)],record[two(15)];
VS M;int N;VI ans;
int solve(int now){
    if( now == 0 ) return 0;
    if( memo[now]>=0 )return memo[now];
    memo[now] = 100000;
    REP(i,N)if(contain(now,i)){
        int mask = now ^ two(i);int tmp = solve(mask);
        REP(j,N)if(contain(mask,j))tmp += (M[j][i] - '0');
        if(tmp < memo[now]) {
            memo[now]=tmp ;
            record[now] = mask;
        }
    }
    return memo[now];
}
void cacl(){
    int mask = two(N)-1;
    ans.clear();
    REP(i,N){
        int k = mask ^ record[mask];
        int cnt = -1; while(k>0){k>>=1;cnt++;}
        ans.push_back(cnt);
        mask=record[mask];
    }
}
class CompanyMessages
{
        public:
        vector <int> getRank(vector <string> mes)
        {
               M=mes;N=mes.size();
               memset(memo,-1,sizeof(memo));
               solve(two(N)-1);
               cacl();
               return ans;
        }