状压dp_状压dp入门 - CSDN
精华内容
参与话题
  • 本次博客,主要是给学弟学妹们讲解一下状压dp,不适合有基础的同学观看,可能会浪费时间,因为偏基础 先来最简单的一个吧 http://acm.hdu.edu.cn/showproblem.php?pid=1565hdu 1565 方格取数(1) Time Limit: ...

    本次博客,主要是给学弟学妹们讲解一下状压dp,不适合有基础的同学观看,可能会浪费时间,因为偏基础

    先来最简单的一个吧   http://acm.hdu.edu.cn/showproblem.php?pid=1565 hdu 1565

    方格取数(1)

    Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 11722    Accepted Submission(s): 4391

    Problem Description

    给你一个n*n的格子的棋盘,每个格子里面有一个非负数。
    从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。

    Input

    包括多个测试实例,每个测试实例包括一个整数n 和n*n个非负数(n<=20)

    Output

    对于每个测试实例,输出可能取得的最大的和

    Sample Input

    3 75 15 21 75 15 28 34 70 5

    Sample Output

    188

    首先我们如果不考虑不能取连续的两个数,那么就像是一个数塔一样最简单的dp模型了,相邻的两个数不能取,我们要先理解最基本的状态,在类似状压bfs的时候也可以类比出来,再推一道很基本的状压bfs:http://acm.hdu.edu.cn/showproblem.php?pid=1429

    那么我们可以对每一列,设为二进制状态,因为n比较少,最多也就(1 << 17) 

    如果第i行状态为11001,那么说明我们第i行取得是1,4,5位置,那么对于第i行我们可以取这个状态,只与第i - 1行取得什么状态有关,如果第i - 1行的状态为y,要取第i行为x,那么一定要(x & y) == 0才满足不取相邻的两个(具体就是二进制位上不能有相同的1,利用&的特性,很容易理解),方程也很容易可以得到f[i][j]代表第i行取j这个状态,然后可以枚举第i - 1行的状态,在枚举第i行的状态,并且不冲突即可。当然我们暴力枚举时间复杂度是多少呢?显然是n*(1 << n)*(1 << n) ,复杂度肯定会挂,然而我们还需要考虑,因为我们每一行对于这个状态,都不能有相邻的两个1,对吧?

    所以需要我们需要保存一些合法的状态,这个可以打表看一下最多有多少个(其实这个n根本就没有20,不然平方级别17000 * 17000 * 20还可以过5s么,亲测了一下,n只有16)

    所以就是 2584 * 2584 * 16,所以复杂度现在就解决了,至于去除不合法的状态,就很简单了,(i & (i >> 1) )== 0则证明是合法状态,因为i往后搓一位后,如果还没有和i有重叠的1,那肯定都是合法的。

    代码:

    int a[19][1 << 17];
    int f[19][1<<17];
    int tot[maxn];
    int calc(int i,int x){
        int cnt = 1,res = 0;
        while(x){
            if(x & 1)  res += a[i][cnt];
            x /= 2;cnt++;
        }
        return res;
    }
    int main()
    {
        ios::sync_with_stdio(false);
        int n;
        while(cin >> n){
    //        if(n >= 17){   while(1){   } }
            int cnt = 0,ans = 0;
            for(int i = 0;i < (1 << n);i++)   if((i & (i >> 1)) == 0) tot[++cnt] = i;
            for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) cin >> a[i][j];
            MS0(f);
            for(int i = 1;i <= n;i++){
                for(int k = 1;k <= cnt;k++){
                    int val = calc(i,tot[k]);
                    for(int j = 1;j <= cnt;j++){
                        if((tot[j] & tot[k]) == 0){
                            f[i][k] = max(f[i][k],f[i - 1][j] + val);
                        }
                    }
                }
            }
            for(int j = 1;j <= cnt;j++)  ans = max(ans,f[n][j]);
            cout << ans << endl;
        }
        return 0;
    }

     

    另外学习了上面的题,再来一个类似的, poj 1185 http://poj.org/problem?id=1185

    炮兵阵地

    Time Limit: 2000MS   Memory Limit: 65536K
    Total Submissions: 34387   Accepted: 13208

    Description

    司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 


    如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 
    现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。 

    Input

    第一行包含两个由空格分割开的正整数,分别表示N和M; 
    接下来的N行,每一行含有连续的M个字符('P'或者'H'),中间没有空格。按顺序表示地图中每一行的数据。N <= 100;M <= 10。

    Output

    仅一行,包含一个整数K,表示最多能摆放的炮兵部队的数量。

    Sample Input

    5 4
    PHPP
    PPHH
    PPPP
    PHPP
    PHHP

    我们再看这个题,只有P位置才可以放炮台,并且其他位置距离2的位置都会被占领,和刚刚的题很类似,刚刚的第i行只和i - 1有关,这个则与i - 1和i - 2有关,显然就多了以一维dp,那还是首先把所有合法的状态找出来,和刚刚的一样操作,定义f[i][j][k]状态为:第i行状态为j,第i - 1行状态为k的能放炮兵的个数。现在就又可以枚举第i行的第j个状态,另外再接着枚举第i - 1行的状态和第i - 2行的状态,首先先要check(j)这个状态是不是合法的,这个合法代表的是选取的每一位是否和第i行的位置对应并且他们都有p,或者这个状态是所有p的子集,一种方法,暴力挨个位数判断,那我们对于每个状态都要判断,第i、i - 1、i - 2,所以就会再复杂度上再加上一个级别

    现在我们考虑怎么优化,我们可以把第i行的状态预处理出来,即有P的地方都变为1,处理出op[i],代表第i行的全集,那么op[i] & j 如果>0则可以表示与第i行的P的位置有冲突 其他的i - 1和i - 2一样的道理

    那么我们可以列出方程

    j 为 第i行的状态,k为第i - 1行的状态,p为i - 2行的状态,num则是j状态1的个数,就是选了多少个P,对于这个num,我们可以用暴力算出二进制1的个数从而得来,但是我们对这里也可以进行一个优化

    f[i][j][k] = max(f[i][j][k],f[i - 1][k][p] + num)

    现在问题就来到了能不能O1时间内得到x的二进制1的个数,那么我们可以根据树状数组的lowbit(x)在O1时间内得到x的末尾0的个数(当然这个(x&(-x))是真的太神奇了),现在我们可以枚举状态到(1 << m),假设

    101100这个1的个数显然可以从101的1的个数+1得来,所以我们可以到i - lowbit(i)得到101的1的个数,并且101的个数是以及枚举过得

    代码:

    char str[190][1 << 10];
    int f[190][80][80];
    int tot[maxn];
    //int f[i][j][k];///第i行,第i行取的状态是j,第i - 1行取得状态是k
    int op[maxn];
    int num[maxn];
    int main()
    {
    //    ios::sync_with_stdio(false);
        int n,m;
        cout << lowbit(3) << endl;
        while(cin >> n >> m){
            int cnt = 0;
            for(int i = 1;i <= n;i++)  scanf("%s",str[i]);
            for(int i = 0;i < (1 << m);i++)     if(((i & (i >> 2)) == 0) && (i & (i >> 1)) == 0) tot[++cnt] = i;
            for(int i = 1;i < (1 << m);i++) {
            num[i] = num[i - lowbit(i)] + 1;
            cout << lowbit(i) << "  ";
            cout << i <<"   " << i - lowbit(i) <<  "    " << num[i] <<endl;
            }
            int ans = 0;
            for(int i = 1;i <= n;i++){
                for(int j = 0;j < m;j++) op[i] |= ((str[i][j] == 'H') << j);
                for(int j = 1;j <= cnt;j++){ ///枚举第i层的状态
                    if((tot[j] & op[i])) continue;
                    for(int k = 1;k <= cnt;k++){///枚举第i - 1的状态
                        if(tot[j] & tot[k]) continue;int val = num[tot[j]];
                        if(i >= 2 && (tot[k] & op[i - 1]))continue;
                        for(int p = 1;p <= cnt;p++){///枚举第i - 2的状态
                            if(tot[p] & op[i - 2]) continue;
                            if((tot[p] & tot[k]) == 0 && (tot[j] & tot[p]) == 0)   f[i][j][k] = max(f[i][j][k],f[i - 1][k][p] + val);
                        }
                        ans = max(f[i][j][k],ans);
                    }
                }
            }
            cout << ans << endl;
        }
        return 0;
    }
    

    最后再来一个例子吧  uva11825

     https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2925

    Miracle Corporations has a number of system services running in a distributed computer system which
    is a prime target for hackers. The system is basically a set of N computer nodes with each of them
    running a set of N services. Note that, the set of services running on every node is same everywhere
    in the network. A hacker can destroy a service by running a specialized exploit for that service in all
    the nodes.
    One day, a smart hacker collects necessary exploits for all these N services and launches an attack
    on the system. He finds a security hole that gives him just enough time to run a single exploit in each
    computer. These exploits have the characteristic that, its successfully infects the computer where it
    was originally run and all the neighbor computers of that node.
    Given a network description, find the maximum number of services that the hacker can damage.
    Input
    There will be multiple test cases in the input file. A test case begins with an integer N (1 ≤ N ≤ 16),
    the number of nodes in the network. The nodes are denoted by 0 to N − 1. Each of the following
    N lines describes the neighbors of a node. Line i (0 ≤ i < N) represents the description of node i.
    The description for node i starts with an integer m (Number of neighbors for node i), followed by m
    integers in the range of 0 to N − 1, each denoting a neighboring node of node i.
    The end of input will be denoted by a case with N = 0. This case should not be processed.
    Output
    For each test case, print a line in the format, ‘Case X: Y ’, where X is the case number & Y is the
    maximum possible number of services that can be damaged.
    Sample Input
    3
    2 1 2
    2 0 2
    2 0 1
    4
    1 1
    1 0
    1 3
    1 2
    0
    Sample Output
    Case 1: 3
    Case 2: 2

    仔细读题,题意描述有点怪,其实就是给你第i个点和与他相邻的点,让你求出他可以最多有多少个没有任何交集的集合,使得任意集合的所有点再加上相邻的点,从而覆盖全部的图,问你最多可以有多少个这样的集合

    对于下面这个图,那他就可以找出3个集合,分别是

    {4,0}、{3,5}、{1,2}

    对这种,我们显然是肯定可以枚举他的子集的,并且再去找与他不相交的集合里,能不能构成覆盖所有点的条件

    我们就可以针对n来枚举子集,看下面这个dfs函数,n代表我取得状态,然后我们再去枚举n的子集,那么枚举n的子集需要多少复杂度呢,最明显的可以用枚举所有状态&n,判断他是不是n的子集,并且再考虑计算,这样的话,复杂度就是2^n,我们最外层枚举n的所有状态又是2^n,这样就得到了4^n,n = 16,所以是不可行的,虽然有的地方我们可以加一个记忆化,但是复杂度还是通过不了的(dfs的复杂度可能不好计算,下面还有一个递推方式的写法)
    int dfs(int n){
        if(f[n] != -1) return f[n];
        int ans = 0;
        for(int i = n;i;i = ((i - 1) & n))   if(check(j)) ans = max(ans,dfs(i ^ n) + 1);
        return f[n] = ans;
    }

                 for(int i = 0; i < (1 << n);i++){
                    int ans = 0;
                    for(int j = i;j;j = (j - 1) & i){
                     if(check(j)){
                            ans = max(ans,f[i ^ j] + 1);
                        }
                    }
                    f[i] = ans;
                 }

    现在我们来考虑怎么优化,怎么快速的找到i的子集呢,假如我们枚举所有的状态, 那么就会出现很多浪费枚举的时候,所以我们可以用一个特别巧妙地方法我们知道 i & n == i 是用来判断i是否是n的子集的(具体是为什么,写一下就知道了),那我们如果想枚举完i的子集,我们可以还是通过i--,来找到i的下一个最近的状态,但是这个i不一定是n的子集,所以我们可以用上面判断的方法来得到最近的符合是n的子集的状态,那就是(i - 1) & n,实在理解不了,就记下来吧。那这样可以优化多少时间复杂度呢

    我们来看递推的dp复杂度,观察第一层for是2^n的复杂度,第2层for是只跟集合的大小有关系的,那么就是有

    C(n,1) + C(n,2) + .... =  ,这样的话,我们考虑大小为i的集合,就有2^i个子集, 那我们现在一起来考虑整个两层for循环的复杂度,就是∑C(n,i) * 2 ^ i,有没有发现这个东西很熟悉,那就是二项式定理了

    所以 ∑C(n,i) * 2 ^ i = 3 ^ i,大小为n的集合就是 3 ^ n,所以现在复杂度就有了

    那我们的check要怎么写的呢,要在O1时间内,check出当前选的状态,可以覆盖完所有的图

    首先我们可以对他输入的边进行处理,因为他出的是第i个点和哪些点有边,所以我们可以先预处理出一个p数组,表示选择i点可以与那些点相连,就是p[i] |= (1 << x),然后我们再来枚举0到(2^n)- 1的所有状态,定义一个arr数组,arr[i],i这个状态可以达到的点都有谁,对于每个状态,我们看看选了哪些点j,arr[i] |= p[j] ,就可以得到当前i状态可以达到的所有点的状态,那判断的时候,arr[i] == (1 << n) - 1 就可以表示所有的图的点都可以被覆盖了

    代码:

    int f[maxn];int k;
    int p[maxn],arr[maxn];
    int dfs(int n){
        if(f[n] != -1) return f[n];
        int ans = 0;
        for(int i = n;i;i = ((i - 1) & n))   if(arr[i] == ((1 << (k)) - 1)) ans = max(ans,dfs(i ^ n) + 1);
        return f[n] = ans;
    }
    int main()
    {
        int n;
        int cas = 1;
        while(cin >> n){
            k = n;
            if(n == 0) break;
            MS1(f); MS0(p);MS0(arr);
            int m,x;
            for(int i = 0;i < n;i++){
                cin >> m;
                p[i] = (1 << i);
                for(int j = 1;j <= m;j++){
                    cin >> x;
                    p[i] |= (1 << x);
                }
            }
             for(int i = 0; i < (1 << n);i++){ ///2 ^ n
                    for(int j = 0;j < n;j++){
                        if(i & (1 << j)) arr[i] |= p[j];
                    }
             }
             /**
                 for(int i = 0; i < (1 << n);i++){
                    int ans = 0;
                    for(int j = i;j;j = (j - 1) & i){
                        if(arr[j] == (1 << n) - 1){
                            ans = max(ans,f[i ^ j] + 1);
                        }
                    }
                    f[i] = ans;
                 }
             */
             dfs((1 << n)- 1);
             printf("Case %d: %d\n",cas++,f[(1 << n) - 1] );
        }
        return 0;
    }

     

    展开全文
  • 状态压缩dp(状压dp)

    万次阅读 多人点赞 2019-02-28 21:28:12
    状压dp是一类比较难理解的dp; 在讲状压dp之前,我们应该清楚所有的dp是解决多阶段决策最优化问题的一种思想方法; 请注意多阶段这三个字: 经过前面三种背包的学习,可以发现如何定义状态是解决动态规划最重要的...

    注:在涉及到位运算时,一定要注意位运算的优先级。该加的括号一定要加

    状压dp是一类比较难理解的dp;

    在讲状压dp之前,我们应该清楚所有的dp是解决多阶段决策最优化问题的一种思想方法;

    请注意多阶段这三个字:

    经过前面三种背包的学习,可以发现如何定义状态是解决动态规划最重要的一步;

    状态的定义也就决定了相当于阶段的划分;

    在背包问题中,我们通过物品的件数i和背包的容量j来定义状态或者说是划分阶段;

    动态规划多阶段一个重要的特性就是无后效性。无后效性就是值对于某个给定的阶段状态,它以前各阶段的状态无法

    直接影响它未来的发展,而只能通过当前的这个状态。换句话说影响当前阶段状态只可能是前一阶段的状态

    那么可以看出如何定义状态是至关重要的,因为状态决定了阶段的划分,阶段的划分保证了无后效性

    ————————————————————————————————————————————————————

    以上讲了一些基本的概念,以下具体用一个例子和一些习题讲一下状压dp;

    有时候为了达到最优子结构和无后效性的效果,我们必须要定义好状态。但是有时候状态维度特别多,但是每个状态的

    决策又很少,这样我们开多维数组很可能会浪费,并且可能会爆空间。

    这时候我们考虑用状态压缩来做,比如每个状态的决策只有两个,但是状态的维度很多。下面我们用01背包来举例。

    有n件物品和一个容量为v的背包。放入第i件物品的占的空间为Ci,得到的价值是Wi;求解每种放法的背包价值;

    (当然这不是一个典型的动态规划问题,但是用动态规划的思想有助于讲解状压dp);

     

    想一想之前动态规划框架讲解,解决动态规划问题首先要定义状态;

    1.定义状态:因为这个要求每一种放法的背包价值,所以我们状态应该是这n件物品的放与不放的情况。

                         最容易想到的是开个n维数组,第i个维度的下标如果是1的话代表放第i件物品,0的话代表不放第i件物品;

                         但是这样很容易造成空间浪费,而且多维数组也不好开;

                         我们仔细观察就会发现,每件物品有放与不放两种选择;假设我们有5件物品的时候,用1和0代表放和不放

                         如果这5件物品都不放的话,那就是00000;

                         如果这5件物品都放的话,    那就是11111;

                        看到这,我们知道可以用二进制表示所有物品的放与不放的情况;如果这些二进制用十进制表示的话就只有

                        一个维度了。而且这一个维度能表示所有物品放与不放的情况;这个过程就叫做状态压缩;

                       细节:观察可以知道在上面的例子中00000 ~ 11111可以代表所有的情况,转化为十进制就是0~(1<<5  - 1);

    2.描述不同状态如何转移:

                       放的状态只能从不放的状态转移过来,所以dp[10000]只能从dp[00000] + W[1] 转移过来;dp[11000]可以从

                       dp[01000] + W[1]或者dp[10000] + W[2]转移过来.........

    3.按一个方向求出该问题的解

                       该问题并不是一个典型的动态规划问题,所以不用管;

    代码如下:

    #include<stdio.h>
    const int INF = 1 << 15;
    int dp[INF + 10];
    int dp1[INF+ 10] ;	//定义状态 
    void print1(int num);		//打印在状态为num的时候的所有物品放与不放的情况 
    
    /*
    3 6
    2 5
    3 8
    4 9				//一组样例 
    
    0       0       0
    1       5       2
    01      8       3
    11      13      5
    001     9       4
    101     14      6
    011     17      7
    111     22      9
    */ 
    int main()
    {
    	int n,m;
    	while(~scanf("%d%d",&n,&m))
    	{
    		int W[20],C[20];
    		for(int i = 0; i < n; i++)
    		scanf("%d %d",&C[i],&W[i]) ;
    		int res = -1;
    		for(int i = 0; i < (1 << n); i++)
    		{
    			for(int j = 0; j < n; j++)
    			{
    				if(!(i&(1 << j)))		//状态转移 
    				{
    					int temp = i | (1<<j);
    					dp[temp] = dp[i] + W[j];		
    					dp1[temp] = dp1[i] + C[j];
    					
    				}
    			}
    		}
    		for(int i = 0; i < (1 << n); i++)
    		{
    			print1(i);
    			printf("\t%d\t%d\n",dp[i],dp1[i]);		//打印出每种方案的情况,价值 和耗费的空间 
    		}
    		
    	}
    	return 0;
    }
    void print1(int num)
    {
    	int k= 0;
    	if(num == 0)
    	printf("0");
    	for(;(1 << k) <= num; k++)
    	{
    		if(num & (1<<k))
    		printf("1");
    		else
    		printf("0");
    	}
    }

    上面涉及到二进制运算的问题可以看另一篇博客位运算及常用功能

    从上面可以看出:状压dp的特点一般是规模比较小,n一般小于15。而且一般只有两种决策

    ————————————————————————————————————————————————————

    例题1:POJ 2411

    这个题规模比较小,而且每个方格只有两种状态,分别是被覆盖和未被覆盖;

    所以我们考虑用状态压缩dp;

    定义状态:

    我们首先定义状态:dp[j][state],表示能到达第j列,且第j列所有方格的覆盖情况为state时的所有方法数;

    这样我们通过这个状态把这个问题分为j个阶段(j代表列数),因为第j列放置的情况最多只能影响到j+1列。比如第j列放置

    一个或多个1*2的方格。这样一种情况就会影响到j+1列;但是他最多影响到第j+1列,之后就不能再影响了。

    这就是无后效性无后效性是保证能动态规划的关键。


    状态转移:

    当第i列第j行状态为0时,表示没有覆盖;当为1时,说明被覆盖了;

    如果当前格没有被覆盖,说明我们至少可以放一个1*2的方格,如果当前列的下一行也没有被覆盖,那么我们可以放一个

    2*1的方格;如果被覆盖, 那么我们继续往当前列的下一行遍历 ,直到把这一列遍历完; 在这个过程中 ,我们能求出

    下一列的合法状态(也就是可以到达的状态),这是一个搜索的过程,至于为什么要搜索,请看下面:

    我们把当前列每一种状态都进行搜索,看能不能找到从这种状态到其他状态的一种路径;如果存在,说明其他状态是

    可以到达的。所以我们其实并不需要对每一种状态进行搜索,只需要对可以到达的状态进行搜索即可;


    按一个方向求出该问题的解:

    当前阶段总是影响下一阶段,所以我们应该按照阶段的方向进行求解,在这个题中是按列的方向求解;题目要求全部填

    满,所以答案应该是dp[m+1][0];


    代码如下:

    #include<stdio.h>
    #include<string.h>
    #define mmset(a,b) memset(a,b,sizeof(a))
    const int INF = 1 << 12 + 10;
    long long dp[13][2100];
    int n,m;
    /*
    1 2
    1 3
    1 4
    2 2
    2 3
    2 4
    2 11
    4 11
    0 0
    Sample Output
    1
    0
    1
    2
    3
    5
    144
    51205
    */
    
    
    /*搜索从第j列的state状态开始,它能到达第j+1列的哪些状态;
      i代表第i行,next代表它能到达第j+1列的next状态 
    */
    void dfs(int i,int j,int state,int next);		
    											    
    int main()
    {
    	
    	while(~scanf("%d%d",&n,&m) && (n+m))
    	{
    		if(n > m)	//交换两个变量 
    		{
    			n = n ^ m;
    			m = n ^ m;
    			n = n ^ m; 
    		}
    		mmset(dp,0);	//初始化 
    		dp[1][0] = 1;
    		
    		for(int j = 1; j <= m; j++)		//状态转移 
    		{
    			for(int state = 0; state < (1 << n); state++)
    			{
    				//对能达到的状态进行搜索,看该状态能不能达到其他状态;
    				if(dp[j][state] > 0)	 
    				{
    					dfs(0,j,state,0);
    				}
    			}
    		} 
    		printf("%lld\n",dp[m+1][0]);		//输出答案 
    		
    		
    	}
    	return 0;
    } 
    
    void dfs(int i,int j,int state, int next)
    {
    	if(i == n)
    	{
    		/*
    		注意dp[i][j]代表的含义,就知道为什么
    		dp[j+1][next] += dp[j][state]
    		*/
    		dp[j+1][next] += dp[j][state];		
    		return;								
    	}
    	else
    	{
    		if((state&(1 << i) )== 0)	//当该格子没被覆盖说明可以放一个1*2的木板 
    		{
    			dfs(i+1,j,state,next | (1<< i));
    		}
    		/*
    		当该格子没被覆盖且它下面的格子也没被覆盖 
    		说明可以当一个2*1的木板
    		*/ 
    		if(i + 1 < n &&(state & (1 << i)) == 0 && (state & (1 << (i+1))) == 0)	
    		{																		
    			dfs(i+2,j,state,next);
    		}
    		if((state & (1 << i)) > 0)	//当该格子被覆盖时,说明这个格子什么都不能放 
    		{
    			dfs(i+1,j,state,next);
    		}
    	}
    }
    

     

    ————————————————————————————————————————————————————

    例题2:POJ 3254

    可以发现这个题有如下特征,规模较小,每个方格只有两种状态,可以种玉米和不可以种玉米;

    仍然考虑用状压dp;


    定义状态:

    定义状态dp[i][state]表示能到达第i行,且第i行的所有的种玉米和不种玉米的情况为state时的所有状态数。

    种玉米代表1,不种玉米代表0;

    分析这个状态定义,发现这个状态定义把整个问题分成了n个阶段(代表行数),并且这n个阶段遵循无后效性


    状态转移:

    当前阶段只受前一阶段的影响,当前阶段只能影响到后一阶段。所以状态转移就是把握住当前状态是如何影响后一

    阶段的。在这个题中,我们会发现:

    如果当前阶段的某列土地种了玉米,那么下个阶段的这列土地就不能种玉米。

    另外,如果当前阶段某列土地的前一列土地种了玉米,那么这一列就不能再种玉米了。

    需要注意的是,如果当前阶段的某一列可以种玉米,你可以有两种选择,种或不种。


    按一个方向求解:

    可以看出这个状态定义是按行数分了n个阶段,所以我们应该按照行数来进行求解,根据状态定义,结果是把最后

    一行的所有可达到的状态的方法数加和即可。


    代码如下:

    #include<stdio.h>
    #include<string.h>
    #define mmset(a,b) memset(a,b,sizeof(a))
    
    const int INF = 1 << 12 + 5;
    int   dp[15][INF];
    int data[15][15];
    int n,m;		//行列 
    
    /*
    2 3
    1 1 1
    0 1 0
    Sample Output
    9
    */
    
    
    /*
    i代表当前行 
    j代表当前列
    state代表当前行(阶段)的状态 
    next代表下一行(阶段)的可到达状态
    flag代表是上一列是否种了玉米,如果种了玉米,flag =  1,否则等于0; 
    */ 
    void dfs(int i,int j,int state,int next,int flag);
    
    int main()
    {
    	while(~scanf("%d%d",&n,&m))
    	{
    		for(int i = 1; i <= n; i++)
    		{
    			for(int j = 0; j < m; j++)
    			{
    				scanf("%d",&data[i][j]);
    			}
    		}
    		mmset(dp,0);		//初始化 
    		dp[0][0] = 1;	
    		
    		/*
    			遍历每个阶段的所有可达到状态,并搜索这种状态所能到达所有状态 。
    			这是状态转移的过程 
    		*/ 
    		for(int i = 0; i < n; i++)	
    		{
    			for(int state = 0; state < (1<<m); state++)
    			{
    				if(dp[i][state] > 0)
    				{
    					dfs(i,0,state,0,0);
    				}
    			}
    		}
    		int ans = 0;
    		/*
    			求解,对最后一行所有可达到的状态的方法数加和,并存在变量ans中; 
    		*/ 
    		for(int state = 0; state < (1<<m); state++)
    		{
    			if(dp[n][state] > 0)
    			{
    				ans=(ans+dp[n][state])%100000000;
    			}
    		}
    		printf("%d\n",ans);
    	}	
    	
    	return 0;
    }
    
    void dfs(int i,int j,int state,int next,int flag)
    {
    	if(j == m) 
    	{
    		dp[i+1][next] = (dp[i+1][next] + dp[i][state])%100000000;
    	}
    	/*
    	下面这段代码有点绕,可以种玉米是指客观条件,
    	但种不种玉米是主观意愿。 
    	*/ 
    	else
    	{
    		//表示可以种玉米 
    		if(data[i+1][j] == 1 && (state & (1<<j)) == 0 && flag== 0) 
    		{
    			if(flag == 0||flag == 1)    //不种玉米 
    			{
     				dfs(i,j+1,state,next,0);
    			}
    			if(flag == 0)	//种玉米 
    			{
    				dfs(i,j+1,state,next | (1<<j),1);
    			}
    		}
    		//不可以种玉米 
    		else
    		{
    			dfs(i,j+1,state,next,0);
    		}
    	}
    }
    
    

     

     

     

     

    展开全文
  • 状压dp的一点理解

    千次阅读 2017-08-10 23:59:20
    状压dp  此dp可以理解为最暴力的dp,因为他需要遍历每个状态,所以将会出现2^n的情况数量,所以明显的标志就是数据不能太多(好像是 for(s=1;s<(1);s++) { for(i = n-1 ; i >=0;i--) { tem=1;

    博主是初学者,以下仅代表个人观点,若有错误欢迎指出。

    状压dp

          此dp可以理解为最暴力的dp,因为他需要遍历每个状态,所以将会出现2^n的情况数量,所以明显的标志就是数据不能太多(好像是<=16?),然后遍历所有状态的姿势就是用二进制来表示,01串,1表示使用,0表示未使用,就把所有的状态投射到很多二进制的数上(类似于hash?)然后对每个状态找一"些"状态的方法如下代码,即状压dp的精髓!!!


    补充:对位运算要熟练,位运算很重要!位运算很重要!位运算很重要!


    for(s=1;s<(1<<n);s++)
    {
         for(i = n-1 ; i >=0;i--)
        {       
            tem=1<<i;        //  1在某一位,其它位为0
            if(tem & s)         //判断是否能由此种状态达到,即判断当前位是1还是0
            {
                past=s-tem;     //当前位的1变为0即为上一状态
            }    
        }         
    }
    



    展开全文
  • 动态规划之状态压缩dp入门

    万次阅读 多人点赞 2015-02-04 16:02:19
    状态压缩动态规划(简称状压dp)是另一类非常典型的动态规划,通常使用在NP问题的小规模求解中,虽然是指数级别的复杂度,但速度比搜索快,其思想非常值得借鉴。 为了更好的理解状压dp,首先介绍位运算相关的知识。 ...

    状态压缩动态规划(简称状压dp)是另一类非常典型的动态规划,通常使用在NP问题的小规模求解中,虽然是指数级别的复杂度,但速度比搜索快,其思想非常值得借鉴。

    为了更好的理解状压dp,首先介绍位运算相关的知识。

    1.’&’符号,x&y,会将两个十进制数在二进制下进行与运算,然后返回其十进制下的值。例如3(11)&2(10)=2(10)。

    2.’|’符号,x|y,会将两个十进制数在二进制下进行或运算,然后返回其十进制下的值。例如3(11)|2(10)=3(11)。

    3.’^’符号,x^y,会将两个十进制数在二进制下进行异或运算,然后返回其十进制下的值。例如3(11)^2(10)=1(01)。

    4.’<<’符号,左移操作,x<<2,将x在二进制下的每一位向左移动两位,最右边用0填充,x<<2相当于让x乘以4。相应的,’>>’是右移操作,x>>1相当于给x/2,去掉x二进制下的最有一位。

    这四种运算在状压dp中有着广泛的应用,常见的应用如下:

    1.判断一个数字x二进制下第i位是不是等于1。

    方法:if ( ( ( 1 << ( i - 1 ) ) & x ) > 0)

    将1左移i-1位,相当于制造了一个只有第i位上是1,其他位上都是0的二进制数。然后与x做与运算,如果结果>0,说明x第i位上是1,反之则是0。

    2.将一个数字x二进制下第i位更改成1。

    方法:x = x | ( 1<<(i-1) )

    证明方法与1类似,此处不再重复证明。

    3.把一个数字二进制下最靠右的第一个1去掉。

    方法:x=x&(x-1)

    感兴趣的读者可以自行证明。

    位运算在状压dp中用途十分广泛,请看下面的例题。

    【例1】有一个N*M(N<=5,M<=1000)的棋盘,现在有1*2及2*1的小木块无数个,要盖满整个棋盘,有多少种方式?答案只需要mod1,000,000,007即可。

    例如:对于一个2*2的棋盘,有两种方法,一种是使用2个1*2的,一种是使用2个2*1的。

    【算法分析】

    在这道题目中,N和M的范围本应该是一样的,但实际上,N和M的范围却差别甚远,对于这种题目,首先应该想到的就是,正确算法与这两个范围有关!N的范围特别小,因此可以考虑使用状态压缩动态规划的思想,请看下面的图:

     

    假设第一列已经填满,则第二列的摆设方式,只与第一列对第二列的影响有关。同理,第三列的摆设方式也只与第二列对它的影响有关。那么,使用一个长度为N的二进制数state来表示这个影响,例如:4(00100)就表示了图上第二列的状态。

    因此,本题的状态可以这样表示:

    dp[i][state]表示该填充第i列,第i-1列对它的影响是state的时候的方法数。i<=M,0<=state<2N

    对于每一列,情况数也有很多,但由于N很小,所以可以采取搜索的办法去处理。对于每一列,搜索所有可能的放木块的情况,并记录它对下一列的影响,之后更新状态。状态转移方程如下:

    dp[i][state]=∑dp[i-1][pre]每一个pre可以通过填放成为state

    对于每一列的深度优先搜索,写法如下:

    //第i列,枚举到了第j行,当前状态是state,对下一列的影响是nex
    void dfs(int i,int j,int state,int nex)
    {
    	if (j==N)
    	{
    		dp[i+1][nex]+=dp[i][state];
    		dp[i+1][nex]%=mod;
    		return;
    	}
    	//如果这个位置已经被上一列所占用,直接跳过
    	if (((1<<j)&state)>0)
    		dfs(i,j+1,state,nex);
    	//如果这个位置是空的,尝试放一个1*2的
    	if (((1<<j)&state)==0)
    		dfs(i,j+1,state,nex|(1<<j));
    	//如果这个位置以及下一个位置都是空的,尝试放一个2*1的
    	if (j+1<N && ((1<<j)&state)==0 && ((1<<(j+1))&state)==0)
    		dfs(i,j+2,state,nex);
    	return;
    }
    

    状态转移的方式如下:

    for (int i=1;i<=M;i++)
    	{
    		for (int j=0;j<(1<<N);j++)
    		if (dp[i][j])
    		{
    			dfs(i,0,j,0);
    		}
    	}
    

    最终,答案就是dp[M+1][0]。

    【代码实现】

    /*
    ID:aqx
    PROG:铺地砖
    LANG:c++
    */
    //第i列,枚举到了第j行,当前状态是state,对下一列的影响是nex
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    
    using namespace std;
    
    int N, M;
    long long dp[1005][34];
    
    void dfs(int i,int j,int state,int nex)
    {
    	if (j==N)
    	{
    		dp[i+1][nex]+=dp[i][state];
    		return;
    	}
    	//如果这个位置已经被上一列所占用,直接跳过
    	if (((1<<j)&state)>0)
    		dfs(i,j+1,state,nex);
    	//如果这个位置是空的,尝试放一个1*2的
    	if (((1<<j)&state)==0)
    		dfs(i,j+1,state,nex|(1<<j));
    	//如果这个位置以及下一个位置都是空的,尝试放一个2*1的
    	if (j+1<N && ((1<<j)&state)==0 && ((1<<(j+1))&state)==0)
    		dfs(i,j+2,state,nex);
    	return;
    }
    
    int main()
    {
    	while (cin>>N>>M)
    	{
    		memset(dp,0,sizeof(dp));
    		if (N==0 && M==0) break;
    		dp[1][0]=1; 
    		for (int i=1;i<=M;i++)
    		{
    			for (int j=0;j<(1<<N);j++)
    			if (dp[i][j])
    			{
    				dfs(i,0,j,0);
    			}
    		}
    		cout<<dp[M+1][0]<<endl;
    	}
    }
    

    【例2】最小总代价(Vijos-1456)

    题目描述:

    n个人在做传递物品的游戏,编号为1-n。

    游戏规则是这样的:开始时物品可以在任意一人手上,他可把物品传递给其他人中的任意一位;下一个人可以传递给未接过物品的任意一人。

    即物品只能经过同一个人一次,而且每次传递过程都有一个代价;不同的人传给不同的人的代价值之间没有联系;

    求当物品经过所有n个人后,整个过程的总代价是多少。

    输入格式:

    第一行为n,表示共有n个人(16>=n>=2);

    以下为n*n的矩阵,第i+1行、第j列表示物品从编号为i的人传递到编号为j的人所花费的代价,特别的有第i+1行、第i列为-1(因为物品不能自己传给自己),其他数据均为正整数(<=10000)。

    (对于50%的数据,n<=11)。

    输出格式:

    一个数,为最小的代价总和。

    输入样例:

    2

    -1 9794

    2724 –1

    输出样例:

    2724

    【算法分析】

    看到2<=n<=16,应想到此题和状态压缩dp有关。每个人只能够被传递一次,因此使用一个n位二进制数state来表示每个人是否已经被访问过了。但这还不够,因为从这样的状态中,并不能清楚地知道现在物品在谁 的手中,因此,需要在此基础上再增加一个状态now,表示物品在谁的手上。

    dp[state][now]表示每个人是否被传递的状态是state,物品在now的手上的时候,最小的总代价。

    初始状态为:dp[1<<i][i]=0;表示一开始物品在i手中。

    所求状态为:min(dp[(1<<n)-1][j]); 0<=j<n

    状态转移方程是:

    dp[state][now]=min(dp[pre][t]+dist[now][t]);

    pre表示的是能够到达state这个状态的一个状态,t能够传递物品给now且只有二进制下第t位与state不同。

    状态的大小是O((2n)*n),转移复杂度是O(n)。总的时间复杂度是O((2n)*n*n)。

    【代码实现】

    /*
    ID:shijieyywd
    PROG:Vijos-1456
    LANG:c++
    */
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    
    #define MAXN 20
    #define INF 0x3f3f3f3f
    
    using namespace std;
    
    int n;
    int edges[MAXN][MAXN];
    int dp[65546][MAXN];
    
    int min(int a, int b) 
    {
    	if (a == -1) return b;
    	if (b == -1) return a;
    	return a < b ? a : b;
    }
    
    int main() {
    	freopen("p1456.in", "r", stdin);
    	scanf("%d", &n);
    	int t;
    	for (int i = 0; i < n; i++) 
    	{
    		for (int j = 0; j < n; j++) 
    		{
    			scanf("%d", &edges[i][j]);
    		}
    	}
    	memset(dp, -1, sizeof(dp));
    	for (int i = 0; i < n; i++) 
    	{
    		dp[1 << i][i] = 0;
    	}
    	int ans = -1;
    	for (int i = 0; i < 1 << n; i++) 
    	{
    		for (int j = 0; j < n; j++) 
    		{
    			if (dp[i][j] != -1) 
    			{
    				for (int k = 0; k < n; k++) 
    				{
    					if (!(i & (1 << k))) 
    					{
    						dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + edges[j][k]);
    						if ((i | (1 << k)) == (1 << n) - 1) ans = min(ans, dp[i | (1 << k)][k]);
    					}
    				}
    			}
    		}
    	}
    	if (ans != -1)
    		printf("%d\n", ans);
    	else printf("0\n");
    
    	return 0;
    }
    

    【例3】胜利大逃亡(续)(Hdoj-1429)

    题目描述:

    Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……


    这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了带锁的门,钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置,离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次,若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试,Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢,如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。

    输入格式:

    每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图,其中包括:


    . 代表路

    * 代表墙

    @ 代表Ignatius的起始位置

    ^ 代表地牢的出口

    A-J 代表带锁的门,对应的钥匙分别为a-j

    a-j 代表钥匙,对应的门分别为A-J


    每组测试数据之间有一个空行。

    输出格式:

    针对每组测试数据,如果可以成功逃亡,请输出需要多少分钟才能离开,如果不能则输出-1。


    输入样例:

    4 5 17

    @A.B.

    a*.*.

    *..*^

    c..b*

    输出样例:

    16

    【算法分析】

    初看此题感觉十分像是宽度优先搜索(BFS),但搜索的过程中如何表示钥匙的拥有情况,却是个问题。借鉴状态压缩的思想,使用一个10位的二进制数state来表示此刻对10把钥匙的拥有情况,那么,dp[x][y][state]表示到达(x,y),钥匙拥有状况为state的最短路径。另外,需要注意到一旦拥有了某一把钥匙,那个有门的位置就如履平地了。

    代码的实现方式可以采用Spfa求最短路的方式。值得一提的是,Spfa算法本来就是一种求解最短路径问题的动态规划算法,本文假设读者已经非常熟悉Spfa等基础算法,在此处不再赘述。

    状态压缩dp可以出现在各种算法中,本题就是典型的搜索算法和状态压缩dp算法结合的题目。另外,很多状态压缩dp本身就是通过搜索算法实现的状态转移。

    【代码实现】

    /*
    ID:shijieyywd
    PROG:Hdu-1429
    LANG:c++
    */
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <queue>
    
    using namespace std;
    
    struct Node{
    	int x;
    	int y;
    	int step;
    	int key;
    	Node() {}
    	Node(int a, int b, int s, int k) : x(a), y(b), step(s), key(k) {}
    };
    
    int n, m, t;
    int arr[25][25];
    int door[25][25];
    int key[25][25];
    int Go[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    int sx, sy;
    int ex, ey;
    int vis[25][25][1049];
    
    bool canGo(int x, int y, int k) 
    {
    	if (x >= 0 && x < n && y >= 0 && y < m && !arr[x][y]) 
    	{
    		if (vis[x][y][k]) return false;
    		if ((k & door[x][y]) == door[x][y]) return true;
    	}
    	return false;
    }
    
    int bfs() {
    	memset(vis, 0, sizeof(vis));
    	queue<Node> q;
    	Node s = Node(sx, sy, 0, 0);
    	q.push(s);
    	vis[sx][sy][0] = 1;
    	while (!q.empty()) 
    	{
    		Node e = q.front();
    		q.pop();
    		if (e.x == ex && e.y == ey) return e.step;
    		for (int i = 0; i < 4; i++) 
    		{
    			int nx = e.x + Go[i][0];
    			int ny = e.y + Go[i][1];
    			if (canGo(nx, ny, e.key)) 
    			{
    				Node nex = Node(nx, ny, e.step + 1, e.key | key[nx][ny]);
    				vis[nx][ny][nex.key] = 1;
    				q.push(nex);
    			}
    		}
    	}
    	return 0;
    }
    
    int main() {
    	while (~scanf("%d %d %d\n", &n, &m, &t)) 
    	{
    		memset(arr, 0, sizeof(arr));
    		memset(door, 0, sizeof(door));
    		memset(key, 0, sizeof(key));
    		char c;
    		for (int i = 0; i < n; i++) 
    		{
    			for (int j = 0; j < m; j++) 
    			{
    				scanf("%c", &c);
    				if (c == '*') arr[i][j] = 1;
    				else if (c == '@') sx = i, sy = j;
    				else if (c == '^') ex = i, ey = j;
    				else if (c >= 'a' && c <= 'z') key[i][j] = 1 << (c - 'a');
    				else if (c >= 'A' && c <= 'Z') door[i][j] = 1 << (c - 'A');
    			}
    			getchar();
    		}
    		int ans = bfs();
    		if (ans < t && ans) printf("%d\n", ans);
    		else printf("-1\n");
    	}
    	return 0;
    }
    



    展开全文
  • emmm,首先要搞懂状压DP这个东西的时候我们要搞懂状压这个概念,其实就是二进制运算的概念,比较经典的就是我写的一个状压非DP–的题目Even Parity—Uva11464—偶数矩阵: 这是我对与状压非DP的一个做法...
  • 状压dp其实和普通dp没有什么区别,主要差别在于要熟练掌握为运算的处理,我自己在这一方面比较菜, 所以特此总结一下,也方便自己以后查阅。 状压dp主要是将当前比较复杂的状压缩到二进制上表示,一般用于处理这样...
  • 状压DP入门

    千次阅读 2019-04-13 19:52:26
    状态压缩动态规划(简称状压dp)是另一类非常典型的动态规划,通常使用在NP问题的小规模求解中,虽然是指数级别的复杂度,但速度比搜索快,其思想非常值得借鉴。 为了更好的理解状压dp,首先介绍位运算相关的知识...
  • 状压DP(入门)

    千次阅读 2018-08-18 20:54:45
        #include&lt;bits/stdc++.h&gt; using namespace std; const int MAX_N = 20; const int MAX_M = 20;...int dp[MAX_N + 1][1 &lt;&lt; MAX_M]; bool not_intersect(int now, int...
  • 状压dp小结

    千次阅读 2018-11-08 15:50:12
    从铺砖块说起 Pro.现有n∗*∗m的一块地板,需要用1*2的砖块去铺满,中间不能留有空隙。问这样方案有多少种 Sol.这题应该每个人都做过吧qwq,这里用它引入介绍三种写法。 [下面的(i,j)竖放都是指覆盖(i,j)和(i-1,j)...
  • 铺砖问题(状压dp

    千次阅读 2018-09-12 01:24:46
    可是去年看了一周的状压dp,只是对旅行商问题有一点感觉,铺砖问题更是一脑袋浆糊,学的太吃力了,无奈放弃了。今年突然心血来潮,又学了一波,无奈还是卡卡卡到铺砖问题,原来书上的解法是没见过的轮廓线动态规划...
  • |算法讨论|状压DP/位运算 学习笔记

    千次阅读 2017-03-05 21:27:18
    [状压DP]poj 3311:经典TSP问题模板及讲解状态压缩动态规划就是用于某种时候DP的状态难以表示时,使用二进制进行存储状态的一种动态规划。通常会用位运算进行操作: 位运算: 1、对xx取反:~x 2、x+1(x为偶数)x+1...
  • 【总结】状压DP

    2017-11-01 21:58:43
    对于状压DP的理解和总结 一般来说,状压是把多种状态(方案,集合等等)hash进二进制数中,0表示该状态不存在,1表示该状态存在(也有用三进制等等,如算路径一点可经过2次),所以首先应掌握位运算。 到目前为止...
  • 关于状压DP枚举子集的方法与理解

    千次阅读 2018-08-11 09:03:32
    刚才发现自己已经不记得如何枚举一个状压集合的子集(因为之前本身就没有怎么理解枚举子集的方法完全就是背下来的所以忘掉很正常),所以写下这篇博客做个提醒或者叫做警示吧,很多东西还是要理解透彻不然会吃亏的。...
  • 把Leetcode上面几道和DP有关的题整理了一下放到一起,先Po出一部分,剩下有时间放上来 DP比较常用的就是利用数组和矩阵Cache了,有很多经典的题是和String结合的,所以要明白用矩阵表示String的含义 我们先从...
  • 状压dp专题----2017.10.1

    千次阅读 2017-10-09 16:31:10
    前言没有前言 T1 Hie with the Pie 题意 解析 代码 提示 出处 T2 Doing Homework 题意 解析 代码 提示 出处 T3 Card Collector ... 给你几个点,每个点都有到其他点的价值,请问遍历所有点的最小价值. ... 最短
  • Codeforces 1051D Bicolorings 简单状压dp

    万次阅读 2018-09-26 13:40:54
    可以作为状压dp的入门题. 由于连通块构成需要相邻,只有上一列的两个格子的颜色对这一列构成连通块的个数有影响. 两个格子的颜色的情况只有4种可能,可以状压这两个格子的涂色方法. 用dp[i][j][k]表示当前涂到iii列,有...
  • 所以肯定是组合数、状压DP什么的,尤其是那个16,标准的状压数。 好吧,就是状压DP。 f[i][j]表示i是状压的01串表示哪个取了哪个没取,然后j是结尾字符, 虽然水,但是时间复杂度是可以过的。 代码: #...
  • 女友ACM训练计划

    千次阅读 2020-01-10 13:11:08
    dp: 最长上升子序列: hdu 1950 代码 最长公共子序列 hdu 1159 代码 状压dp: TSP问题/货郎担问题 hdu 5418 代码 小练习: P1439 【模板】最长公共子序列 代码
  • 状压DP问题

    千次阅读 2015-10-06 11:23:36
    状态压缩·一题目传送:#1044 : 状态压缩·一AC代码:#include #include #include #include #include #include #include #include #include #include #in
  • TSP问题(状压DP求解)

    千次阅读 2017-03-13 13:46:28
    白书上介绍了一种很经典的状压dp求解方法.  dp[s][v],s表示一个点的集合,这个集合可以是DAG中所有点的子集,这里我们用s来代表所有已经到过的点,用dp[s][v](v∈s)代表从v点出发经过除s以外的所有点后
1 2 3 4 5 ... 20
收藏数 18,886
精华内容 7,554
关键字:

状压dp