TC-05TCOR4-250 DP

Posted on 2009-11-22 15:58 rikisand 阅读(193) 评论(0)  编辑 收藏 引用 所属分类: TopcoderAlgorithm
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;
        }

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理