• <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 閱讀(206) 評論(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;
                    }
            久久久久久久99精品免费观看| 91精品国产综合久久精品| 91精品国产综合久久精品| 久久av无码专区亚洲av桃花岛| 久久精品国产免费一区| 久久精品国产亚洲av瑜伽| 色综合久久88色综合天天 | 狠狠色噜噜色狠狠狠综合久久| 久久精品国产亚洲AV无码麻豆 | 久久久久亚洲精品无码网址 | 久久99国产一区二区三区| 综合久久给合久久狠狠狠97色| 久久亚洲精品无码VA大香大香| 久久午夜羞羞影院免费观看| 99久久精品国产综合一区 | 久久精品国产亚洲麻豆| 欧美激情精品久久久久久久九九九| 要久久爱在线免费观看| 久久综合综合久久97色| 久久久久久精品无码人妻| 大蕉久久伊人中文字幕| 人妻无码中文久久久久专区| 久久综合伊人77777麻豆| 精品蜜臀久久久久99网站| 色播久久人人爽人人爽人人片AV| 99久久婷婷免费国产综合精品| 伊人色综合久久天天网| 久久精品国产一区二区三区| 国产精品一区二区久久国产| 日韩欧美亚洲综合久久| 婷婷久久精品国产| 久久99国产精品成人欧美| 国产 亚洲 欧美 另类 久久| 国产精品久久久久无码av| 亚洲欧美日韩久久精品第一区| 中文字幕无码久久精品青草| 国产成人精品久久| 久久久久99精品成人片| 国产精品99久久精品爆乳| 91精品无码久久久久久五月天| 国产精品福利一区二区久久|