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'.

按照題目說明可知，按照找到的順序，所有從低級(jí)向高級(jí)發(fā)的信得數(shù)目和應(yīng)該是最小的。又觀察到，只要確定了第一個(gè)，也就是級(jí)別最高的boss，那么剩下的員工怎么排列，他們向最高boss 發(fā)信數(shù)是不變的，從而子問題就是在剩下員工中找到 低級(jí)向高級(jí)發(fā)信數(shù)最小的排列 ，顯然這符合DP問題最優(yōu)子結(jié)構(gòu)的問題。

T[1···N]=Min{sum(N <->{1-N-1},T[1-N-1] } 得到狀態(tài)方程后很容易寫出程序 ，可以使用備忘錄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;
        }