经典的状态压缩DP,《算法艺术与信息学竞赛》的例题。f[i][j]表示前i行,最后两行状态为二进制数j,嵌入的最多芯片数。第i行到第i+1行用DFS进行状态转移。
由于第i+1行只和第i行有关,故可以用滚动数组优化。

/*************************************************************************
Author: WHU_GCC
Created Time: 2000-9-12 11:08:54
File Name: pku1038.cpp
Description: 
***********************************************************************
*/

#include 
<iostream>
using namespace std;

#define out(x) (cout << #x << ": " << x << endl)
typedef 
long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template 
<class T> void show(T a, int n) for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template 
<class T> void show(T a, int r, int l) for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

const int maxn = 150;
const int maxm = 10;

int n, m, k;
int g[maxn];

int cnt_mask;
int mask[30];

int f[2][1 << (2 * maxm)];

void generate_mask()
{
    cnt_mask 
= 0;
    
for (int i = 0; i < m - 2; i++)
    
{
        
int tmp = 0;
        tmp 
|= 7 << (2 * m + i);
        tmp 
|= 7 << (m + i);
        mask[cnt_mask
++= tmp;
        tmp 
= 0;
        tmp 
|= 7 << (m + i);
        tmp 
|= 7 << (i);
        mask[cnt_mask
++= tmp;
    }

    
for (int i = 0; i < m - 1; i++)
    
{
        
int tmp = 0;
        tmp 
|= 3 << (2 * m + i);
        tmp 
|= 3 << (m + i);
        tmp 
|= 3 << (i);
        mask[cnt_mask
++= tmp;
    }

}


void dfs(int row, int org_t, int now_t, int now, int cnt)
{
    f[(row 
+ 1% 2][now_t & ((1 << (2 * m)) - 1)] >?= f[row % 2][org_t] + cnt;
    
for (int i = now; i < cnt_mask; i++)
        
if ((now_t & mask[i]) == 0)
            dfs(row, org_t, now_t 
| mask[i], i + 1, cnt + 1);
}


int dp()
{
    memset(f, 
-1sizeof(f));
    f[
1][(g[0<< m) | g[1]] = 0;

    
int end = (1 << (2 * m));
    
for (int i = 1; i < n - 1; i++)
    
{
        
for (int j = 0; j < end; j++if (f[i % 2][j] != -1)
        
{
            
int t = (j << m) | g[i + 1];
            dfs(i, j, t, 
00);
        }

        memset(f[i 
% 2], -1sizeof(f[i % 2]));
    }

    
int ret = 0;
    
for (int i = 0; i < end; i++)
        ret 
>?= f[(n - 1% 2][i];
    
return ret;
}


int main()
{
    
int ca;
    
for (scanf("%d"&ca); ca--;)
    
{
        scanf(
"%d%d%d"&n, &m ,&k);
        memset(g, 
0sizeof(g));
        
for (int i = 0; i < k; i++)
        
{
            
int x, y;
            scanf(
"%d%d"&x, &y);
            g[x 
- 1|= 1 << (y - 1);
        }

        generate_mask();
        printf(
"%d\n", dp());
    }

    
return 0;
}
posted on 2007-09-12 20:44 Felicia 阅读(1479) 评论(3)  编辑 收藏 引用 所属分类: 动态规划
Comments
  • # re: [动态规划]pku1038
    Run&Run
    Posted @ 2007-11-21 15:41
    大牛同志,你的方法和<<算法艺术与信息学竞赛上>>写的不太一样....
    状态压缩的DP......研究了我足足5个小时才看明白.....
    你开头的解释也太少了吧,光那个mask[]就想了我快两个小时.
    你要照顾新人撒,多写点解释撒.
    话说回来,你位运算确实用得出神入化,佩服!  回复  更多评论   
  • # re: [动态规划]pku1038
    Felicia
    Posted @ 2007-11-21 15:44
    mask表示所有可能的放置情况  回复  更多评论   
  • # re: [动态规划]pku1038
    prister
    Posted @ 2016-05-18 01:05
    @Run&amp;Run
    里面的两处>?=是什么意思  回复  更多评论   

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理