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

            久久久久久国产精品无码下载| 精品久久久久久国产潘金莲| 欧美精品福利视频一区二区三区久久久精品 | 久久嫩草影院免费看夜色| 久久午夜福利电影| 无遮挡粉嫩小泬久久久久久久 | 久久露脸国产精品| 国产成人无码精品久久久性色| 久久精品国产网红主播| 亚洲第一永久AV网站久久精品男人的天堂AV| 四虎国产精品免费久久| 99久久婷婷免费国产综合精品| 久久无码人妻精品一区二区三区| 久久久精品2019免费观看| 日韩精品无码久久一区二区三| 粉嫩小泬无遮挡久久久久久| 2021国产精品午夜久久| 国产成人99久久亚洲综合精品| 亚洲愉拍99热成人精品热久久| 久久99精品久久久久久9蜜桃| 精品久久久久久成人AV| 久久狠狠爱亚洲综合影院| 久久一区二区三区免费| 热99re久久国超精品首页| 69国产成人综合久久精品| 亚洲综合伊人久久大杳蕉| 亚洲午夜福利精品久久| 久久久WWW成人免费毛片| 国产AV影片久久久久久| 97超级碰碰碰碰久久久久| 久久精品国产99国产精偷| 久久精品国产精品亚洲毛片| 久久久久亚洲精品天堂| 久久精品国产亚洲AV香蕉| 久久久久久精品免费看SSS| 伊人久久久AV老熟妇色| 久久无码AV中文出轨人妻| 99蜜桃臀久久久欧美精品网站| 久久久久免费精品国产| 久久久久人妻一区精品性色av| 精品永久久福利一区二区|