• <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>

            misschuer

            常用鏈接

            統(tǒng)計(jì)

            積分與排名

            百事通

            最新評(píng)論

            hdu 1074 Doing Homework

            #include <iostream>
            #define MAXM 1 << 16
            #include 
            <vector>
            #include 
            <cmath>
            #define MAXN 16
            #include 
            <string>
            using namespace std;

            typedef 
            struct {
                
                
            string obj;
                
            int deadline;
                
            int needday;
            }Point;
            //所需天數(shù), 前一個(gè)狀態(tài), 最少損失.
            typedef struct {
                
                
            int nedday;
                
            int fStatus;
                
            int lostScore;
            }Node;

            Point p[MAXN];

            Node dp[MAXM];
            bool vist[MAXM];
            int n;

            void print(int status) {

                vector
            <string> V;
                
            int pre = status;

                
            while(dp[status].fStatus != -1) {
                
                    
            int crr = dp[status].fStatus;
                    
            int s = crr ^ pre;

                    
            int cc = log(s + 0.00000001/ log(2.0);

                    V.push_back(p[ cc ].obj);
                    pre 
            = crr;
                    status 
            = pre;
                }

                
            for(int i = V.size() - 1; i >= 0-- i) {
                
                    cout 
            << V[ i ] << endl;
                }
            }

            void res() {
                
                memset(vist, 
            falsesizeof(vist));
                dp[ 
            0 ].nedday = 0;
                dp[ 
            0 ].fStatus = -1;
                dp[ 
            0 ].lostScore = 0;
                
                
            int upper = (1 << n) - 1;
                
                
            for(int j = 0; j < upper; ++ j) {
                    
                    
            for(int i = 0; i < n; ++ i) {
                        
                        
            int crr = 1 << i;

                        
            if((crr & j) == 0) {

                            
            //作業(yè)i完成時(shí)的狀態(tài)
                            int curtmp = (crr | j);

                            
            //作業(yè)i完成時(shí)消耗的時(shí)間
                            dp[curtmp].nedday = dp[ j ].nedday + p[ i ].needday;
                            
                            
            //作業(yè)i完成時(shí)超期的時(shí)間
                            int reduce = dp[curtmp].nedday - p[ i ].deadline;
                            
                            
            //若不超期
                            if(reduce < 0) reduce = 0;

                            
            //累加前一個(gè)狀態(tài)的超期時(shí)間
                            reduce += dp[ j ].lostScore;

                            
                            
            if(vist[curtmp]) {
                                
                                
            //該狀態(tài)訪問(wèn)過(guò)
                                if(reduce < dp[curtmp].lostScore) {
                                
                                    dp[curtmp].lostScore 
            = reduce;
                                    dp[curtmp].fStatus 
            = j;
                                }
                            }
                            
            else if(!vist[curtmp]) {
                                
                                
            //該狀態(tài)尚未訪問(wèn)
                                    vist[curtmp] = true;
                                    dp[curtmp].lostScore 
            = reduce;
                                    dp[curtmp].fStatus 
            = j;
                            }
                        }
                    }
                }

                printf(
            "%d\n", dp[upper].lostScore);
                
                
            /*
                for(int i = 0; i <= upper; ++ i) {
                
                    cout << i << " " << dp[ i ].fStatus << " " << dp[ i ].lostScore << " " << dp[ i ].nedday << endl;
                }
                
            */

                print(upper);
            }

            int main() {
                
                
            int test;
                cin 
            >> test;
                
                
            while(test --) {
                    
                    cin 
            >> n;
                    
            for(int i = 0; i < n; ++ i) {
                        
                        cin 
            >> p[ i ].obj >> p[ i ].deadline >> p[ i ].needday;
                    }
                    
                    res();
                }
                
            return 0;

            posted on 2011-03-13 20:58 此最相思 閱讀(246) 評(píng)論(0)  編輯 收藏 引用


            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            国内精品久久久久久99蜜桃| 久久99国产精品久久久| 国产精品久久亚洲不卡动漫| 国产成人无码精品久久久性色| 久久九九久精品国产| 91精品国产综合久久四虎久久无码一级| 久久久久久久久波多野高潮| 伊人久久大香线蕉精品不卡| 国产精品青草久久久久福利99| 国产99久久九九精品无码| 久久亚洲国产精品一区二区| 久久综合久久综合久久| 国内精品久久久久久久涩爱| 久久99热这里只有精品国产| 久久久久香蕉视频| 久久综合九色综合久99| 久久国内免费视频| 亚洲国产欧洲综合997久久| 香蕉久久av一区二区三区| 亚洲精品乱码久久久久久久久久久久 | 久久久久久久综合狠狠综合| 亚洲中文字幕伊人久久无码| 久久人人爽人人人人片av| 99久久国产宗和精品1上映| 亚洲国产精品无码久久| 国内精品人妻无码久久久影院| 国产成人久久精品二区三区| 亚洲国产成人精品91久久久| 午夜精品久久久久久久久| 久久国产精品无码一区二区三区 | 嫩草影院久久99| 欧美性大战久久久久久| 久久久久久亚洲Av无码精品专口 | 久久国语露脸国产精品电影| 97久久精品人人澡人人爽| AV无码久久久久不卡蜜桃| 久久er99热精品一区二区| 国产精品久久网| 久久这里只有精品视频99| 麻豆精品久久久久久久99蜜桃| 亚洲色婷婷综合久久|