• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            TC-05TCOR4-250 DP

            Posted on 2009-11-22 15:58 rikisand 閱讀(204) 評論(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'.

            按照題目說明可知,按照找到的順序,所有從低級向高級發(fā)的信得數目和應該是最小的。又觀察到,只要確定了第一個,也就是級別最高的boss,那么剩下的員工怎么排列,他們向最高boss 發(fā)信數是不變的,從而子問題就是在剩下員工中找到 低級向高級發(fā)信數最小的排列 ,顯然這符合DP問題最優(yō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;
                    }
            中文字幕亚洲综合久久2| 一级做a爰片久久毛片看看| 久久精品人成免费| 91精品国产高清久久久久久io| 国产精品久久久久久一区二区三区| 亚洲综合精品香蕉久久网97| 久久久久亚洲精品中文字幕| 久久久久久伊人高潮影院| 2021久久国自产拍精品| 久久av免费天堂小草播放| 亚洲人AV永久一区二区三区久久| 久久人妻少妇嫩草AV无码专区| 国产AⅤ精品一区二区三区久久 | 精品久久无码中文字幕| 国产精品欧美久久久久天天影视 | 亚洲精品第一综合99久久| MM131亚洲国产美女久久| 日韩人妻无码一区二区三区久久99| 久久国产精品99精品国产| 久久亚洲国产最新网站| 久久精品免费网站网| 2022年国产精品久久久久| 蜜桃麻豆WWW久久囤产精品| 精品多毛少妇人妻AV免费久久| 亚洲AV无码一区东京热久久| 午夜精品久久久久9999高清| 夜夜亚洲天天久久| 国产一区二区三区久久| 精品久久久久久国产潘金莲 | 久久se精品一区精品二区| 亚洲午夜久久久久久噜噜噜| 久久亚洲国产最新网站| 亚洲精品99久久久久中文字幕| 久久精品人妻一区二区三区| 久久久久亚洲AV无码专区桃色| 伊人久久大香线蕉影院95| 国产激情久久久久影院| 久久久久国产| 色综合久久夜色精品国产| 国产亚洲精久久久久久无码77777| 中文字幕日本人妻久久久免费|