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

            Why so serious? --[NKU]schindlerlee

            2010年1月13日星期三.pku1185 狀態(tài)壓縮動(dòng)態(tài)規(guī)劃

            2010年1月13日星期三.pku1185
            狀態(tài)壓縮動(dòng)態(tài)規(guī)劃

            pku1185:題目是中文的,而且題目很經(jīng)典,題意不再贅述。

            這個(gè)題目比pku2411和sgu131兩題來說多了一行狀態(tài)需要儲(chǔ)存
            因?yàn)槿绻仙闲泻痛诵杏嘘P(guān)
            而且此題不再是求完美覆蓋的方式,而是求能最大的放置個(gè)數(shù)。

            方法是先求出一行中的所有放置方法。
            然后逐行遞推,然后在遞推的過程中枚舉當(dāng)前行狀態(tài),如果和上兩行不沖突的話,就
            進(jìn)行放置個(gè)數(shù)的更新

            f[N][60][60] //N行,上一行的狀態(tài)號(hào),上上行的狀態(tài)號(hào)

            具體看代碼吧
              1 
              2 /*
              3  * SOUR:pku1185
              4  * ALGO:State Compression DP
              5  * DATE: 2010年 01月 13日 星期三 13:57:49 CST
              6  * COMM:4 http://m.shnenglu.com/schindlerlee
              7  * */
              8 #include<iostream>
              9 #include<cstdio>
             10 #include<cstdlib>
             11 #include<cstring>
             12 #include<algorithm>
             13 using namespace std;
             14 typedef long long LL;
             15 const int maxint = 0x7fffffff;
             16 const long long max64 = 0x7fffffffffffffffll;
             17 
             18 #define bin(i) (1 << (i))
             19 #define low(i) ((i) & -(i))
             20 #define SL(i) ((i) << 1)
             21 #define SR(i) ((i) >> 1)
             22 
             23 void ckmax(int &a, int b)
             24 if (a < b) a = b; }
             25 
             26 const int N = 102;
             27 const int M = 10;
             28 
             29 //60是對M==10的一行進(jìn)行深搜得到的最大狀態(tài)數(shù)量
             30 int f[N][60][60], n, m, terrain[N], full;
             31 int s[60], top, c[60];
             32 
             33 int legal(int x)
             34 {
             35     int b = 0, cnt = 0, c;
             36     while (x > 0) {
             37         cnt++;
             38         c = low(x);
             39         if (SL(b) & x || SL(SL(b)) & x) {
             40             return -1;
             41         }
             42         x ^= c;
             43         b = c;
             44     }
             45     return cnt;
             46 }
             47 
             48 void preprocess()
             49 {
             50     int i, j, cnt;
             51     for (i = 0; i <= full; i++) {
             52         if ((cnt = legal(i)) >= 0) {
             53             s[top] = i, c[top] = cnt, top++;
             54         }
             55     }
             56 }
             57 
             58 bool contradict(int cur, int s1, int s2)
             59 return (cur & s1) || (cur & s2); }
             60 
             61 int main()
             62 {
             63     int i, j, k;
             64     char str[12];
             65     while (scanf("%d%d\n"&n, &m) == 2) {
             66         full = bin(m) - 1;
             67         preprocess();
             68 
             69         for (i = 1; i <= n; i++) {
             70             scanf("%s\n", str);
             71             int tmp = 0;
             72             for (j = 0; j < m; j++) {
             73                 tmp <<= 1;
             74                 if (str[j] == 'H') {
             75                     tmp |= 1;
             76                 }
             77             }
             78             terrain[i] = tmp;
             79         }
             80 
             81         for (i = 1; i <= n; i++) {
             82             for (j = 0; j < top; j++) { //枚舉當(dāng)前行
             83                 int cur = s[j], curcnt = c[j];
             84                 if (cur & terrain[i]) {
             85                     continue;
             86                 }    //不符合第i行地形要求
             87 
             88                 for (int k1 = 0; k1 < top; k1++) { //枚舉前兩行
             89                     for (int k2 = 0; k2 < top; k2++) {
             90                         if (!contradict(cur, s[k1], s[k2])) { //和上兩行狀態(tài)不沖突
             91                             ckmax(f[i][j][k1], f[i - 1][k1][k2] + curcnt);
             92                         }
             93                     }
             94                 }
             95             }
             96         }
             97 
             98         int res = 0;
             99         for (i = 0; i < top; i++) {
            100             for (j = 0; j < top; j++) {
            101                 ckmax(res, f[n][i][j]);
            102             }
            103         }
            104         printf("%d\n", res);
            105     }
            106     return 0;
            107 }
            108 
            109 


            posted on 2010-01-13 22:25 schindlerlee 閱讀(1051) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 解題報(bào)告

            91精品国产高清91久久久久久| 国产成人无码精品久久久久免费 | 四虎亚洲国产成人久久精品| 久久99精品久久久久久hb无码| 久久人人爽人人爽人人片av麻烦 | 亚洲精品乱码久久久久久蜜桃不卡| 亚洲精品无码久久不卡| 思思久久99热免费精品6| 欧美久久久久久| 久久免费视频1| 人妻无码αv中文字幕久久琪琪布| 久久99精品国产麻豆宅宅| 亚洲精品午夜国产VA久久成人| 精品久久久无码21p发布| 亚洲国产精品18久久久久久| 久久人妻少妇嫩草AV无码专区| 久久99国产综合精品| 91久久精品电影| 无码任你躁久久久久久久| 狠狠色综合网站久久久久久久高清 | 亚洲а∨天堂久久精品| 中文字幕无码精品亚洲资源网久久| 色综合久久无码五十路人妻| 久久青青草原精品影院| 久久精品国产精品亜洲毛片| 狠狠色噜噜色狠狠狠综合久久| 久久久久久毛片免费播放| 国产精品无码久久久久| 国产色综合久久无码有码| 99久久久精品| 狠狠色丁香久久婷婷综合蜜芽五月| 亚洲欧美日韩久久精品第一区| 国产精品免费久久久久电影网| 伊人久久大香线焦AV综合影院| 亚洲国产精品久久久久婷婷老年| 色婷婷久久久SWAG精品| 久久成人国产精品二三区| 久久亚洲AV无码精品色午夜| 国产99久久久久久免费看| 日韩人妻无码精品久久免费一| 国产精品欧美久久久久无广告 |