状压dp入门 - CSDN
精华内容
参与话题
  • 动态规划之状态压缩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;
    }
    



    展开全文
  • 状压DP入门

    千次阅读 2018-08-17 18:29:27
    状压DP: 神奇的DP方式,简单来说就是用二进制来简单压缩状态,然后根据题目可能会有一点点改变。 但是不一定是用二进制,还有一些以压缩状态为思想的题目。 首先参考: ...

    状压DP:

    神奇的DP方式,简单来说就是用二进制来简单压缩状态,然后根据题目可能会有一点点改变。

    但是不一定是用二进制,还有一些以压缩状态为思想的题目。

    首先参考:

    https://blog.csdn.net/Stockholm_Sun/article/details/78213290

    http://www.cnblogs.com/Ronald-MOK1426/p/8451875.html

    https://blog.csdn.net/qq_36183935/article/details/70904217

    https://www.cnblogs.com/Ronald-MOK1426/p/8456945.html

    比较重要的状态转移和状态判断。

    第一道题 洛谷 

    P1879 入门题 Corn Fields

    Description

    Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

    Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

    Input

    Line 1: Two space-separated integers:M and N
    Lines 2..M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)

    Output

    Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.

    Sample Input

    2 3

    1 1 1

    0 1 0

    Sample Output

    9

    Hint

    Number the squares as follows:

    1 2 3

      4 


    There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.

    用二进制存储状态去用上面的各种位运算用于判断,预处理所有状态然后把这些状态依次放进去首先判断满足不相邻条件,再判断是否会与上面相邻,并且用上面的进行转移。

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<map>
    #include<cstdlib>
    #include<cmath>
    #include<set>
    #include<queue>
    #include<vector>
    
    #define MOD 100000000
    
    using namespace std;
    
    int n,m,tot,state[1500],dp[15][1500],ans,cur[15];
    
    bool fit(int x,int k)
    {
    	return !(state[x]&cur[k]);//判断当前状态是否符合当前行 
        //不放牛的地方绝对不可以放牛否则就会为1 
    }
    
    void init()
    {
    	tot=0;
    	int sum=1<<n;  //预处理所有可能状态 
        for(int i=0;i<sum;i++)
        {
        	if(!(i&(i<<1)))state[++tot]=i;//不相邻 
        }
    }
    
    int main()
    {
    	int k;
        cin>>m>>n;
        init();
        for(int i=1;i<=m;i++)
           for(int j=1;j<=n;j++)
           {
           	    cin>>k;
           	    if(!k)
           	    {
        	       	cur[i]+=(1<<(n-j));//当不放牛状态就是1 
                }    
           }
    	for(int i=1;i<=tot;i++)
    	    if(fit(i,1))
    		dp[1][i]=1;
    	for(int i=2;i<=m;i++)//枚举行 
    	    for(int j=1;j<=tot;j++)//枚举当前状态 
    		{
    			if(!fit(j,i))continue;
    			for(k=1;k<=tot;k++)//满足状态后枚举上一层可行状态用于状态转移 
    			{
    				if(!fit(k,i-1))
    				continue;
    				if(state[j]&state[k])//有没有上下相邻 
    				continue;
    				dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD; 
    			}
    		}
    	for(int i=1;i<=tot;i++)
    	    ans=(ans+dp[m][i])%MOD;
    	printf("%d",ans);
    	return 0;	     
    }

    第二道题

     http://www.cnblogs.com/Ronald-MOK1426/p/8456798.html

    【洛谷P1896【SCOI2005】】互不侵犯King

    题目描述

    在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。

    输入输出格式

    输入格式:

    只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)

    输出格式:

    所得的方案数

    输入输出样例

    输入样例#1

    3 2

    输出样例#1

    16

    解题方法差不多也是转移从上一行下来的01串,就是判断是否满足条件多了左上左下等而已。

    事实上,中间有一步我处理重复0的情况不加也能AC,不知道为什么。

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<set>
    #include<map>
    #include<stack>
    
    
    using namespace std; 
    typedef long long LL;
    typedef unsigned long long ULL;
    
    long long state[1500],dp[10][1500][85],n,k,tot,ans=0,king[1500]; 
    
    void init()
    {
    	memset(king,0,sizeof(king));
    	tot=(1<<n)-1;//01串所有的状态 
    	for(int i=0;i<=tot;i++)
    	{
    		if(!((i<<1)&i))//保证没有相邻元素
    		{
    			state[++ans]=i;//状态数 
    			int t=i;
    			while(t)
    			{
    				king[ans]+=t%2;
    				t>>=1;
    			}//取二进制从而判断出国王数量 
    		} 
    	}
    }
    
    int main()
    {
        cin>>n>>k;
    	init();
    	memset(dp,0,sizeof(dp));
    	for(int i=1;i<=ans;i++)
    	{
    		if(king[i]<=k)
    		dp[1][i][king[i]]=1;
    	}
    	for(int i=1;i<=n;i++)
    	{
    		dp[i][1][0]=1;
    	}  //由于重复0情况不能相加,需要主动赋值。 
    	for(int i=2;i<=n;i++)
    	{
    		for(int j=1;j<=ans;j++)
    		{
    			for(int p=1;p<=ans;p++)
    			{
    				if(state[j]&state[p])continue;//上下相邻:j作为这一层状态,p作为上一层状态 
    				if((state[j]<<1)&state[p])continue;//判断有没有右下 
    				if((state[j])&(state[p]<<1))continue;//判断有没有左下 
    				//都只左移是防止状态被去掉 =》这样保证一步步向下推
    				
    				//需要考虑国王数目
    				for(int s=1;s<=k;s++)
    				{
    					if(king[j]+s>k)
    					  continue; 
    					dp[i][j][king[j]+s]+=dp[i-1][p][s];
    				}//枚举这一行状态出现之前已经出现的国王可能数。
    				//i-1行之前比如出现了一个,出现了两个 ,出现了三个,然后加上第i行状态。 
    				//不能枚举0,因为0是无效的,每一行加入0会进行重复加,比如第三行2个然后满了的情况,第一第二行分别会加一种情况,第三行2个加上前两个空的情况就不只是算
    				//一次了,而实际上这只算一次,所以这种0的情况通过初始化第一行,不放元素然后一直不放元素作为1种 
    				
    				//防止重复只能从1开始,但是对于每次这种前面全是0的情况我们需要赋值为一种情况。 
    			}
    		}
    	}
    	
    	LL sum=0;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=ans;j++)
    		{
    			sum+=dp[i][j][k];
    		}
    	} 
    	cout<<sum<<endl;
    }
    

     

    P2704 [NOI2001]炮兵阵地 

    基础偏一点处理

    处理两行的状态,因为需要考虑判断的是左两个(预处理状态的时候就可以排除),还有上面两个,需要存下相邻两行状态,然后递推就可以也满足右下,相当于之后的左上。

    然后动规方程:dp[第i行][第i行状态][第i-1行状态]=max(dp[i][i状态][i-1状态],dp[i-1][i-1状态][i-2状态]+i状态炮兵数目)

    然后第几行需要作为滚动数组,防止MLE,因为其实动规方程递推的时候只需要考虑前一行就可以,dp[2][1<<10+1][1<<10+1]的容量就已经完全满足了。

    细节判定条件和之前基本一致。本题貌似单字符处理会WA,有些玄学,反正我处理这道题花了很久,明明基本都写出来了,都困在字符串处理上,用cin gets getchar 效果有时候居然不同。

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<set>
    #include<map>
    #include<stack>
    
    
    using namespace std; 
    typedef long long LL;
    typedef unsigned long long ULL;
    
    long long dp[3][1<<10][1<<10],num[1<<10];
    long long cur[1<<10+1];
    long long state[1<<10+1];
    int n,m;
    int ans=0;
    int fit(int i,int j)
    {
        return !(state[i]&cur[j]); 
    } //如果!内的项为0 说明没有放错位置。 
    
    void init()
    {
        memset(dp,0,sizeof(dp));
        memset(num,0,sizeof(num));
        memset(cur,0,sizeof(cur));
        int tot=(1<<m)-1;
        for(int i=0;i<=tot;i++)
        {
            if( ( (i<<1)&i)||( (i<<2)&i) )
            {
                ;
            }
            else 
            {
                state[++ans]=i;
                int t=i;
                while(t)
                {
                    num[ans]+=t%2;
                    t>>=1;
                }
            }
        }
    }
    
    int main()
    {
    
        cin>>n>>m;
        init();
        char s[200];
        if(n==0&&m==0)
        {
        	cout<<"0"<<endl;
        	return 0;
        }
        for(int i=1;i<=n;i++)
        {
        	cin>>s;
        	for(int j=0;j<strlen(s);j++)
        	{
            	if(s[j]=='H')
            	cur[i]+=1<<(m-j-1);
            }
        } 
        for(int i=1;i<=ans;i++)
        {
        	if(fit(i,1))
        	dp[1][i][0]=num[i];
        }
        //先处理第二行
        for(int i=1;i<=ans;i++)
         for(int j=1;j<=ans;j++)
         {
            if(fit(i,2)&&fit(j,1))
            if(!(state[i]&state[j]))
            {
              dp[0][i][j]=num[i]+dp[1][j][0];
            //  cout<<dp[0][i][j]<<endl;
              //cout<<dp[2][i][j];
            }
         }
         if(n==1)
         {
        	long long A=0;
        	for(int i=1;i<=ans;i++)
        	{
    	    	if( fit(i,1) )
    	    	A=max(A,num[i]);
    	    }
    	    cout<<A<<endl;
    	    return 0;
         }
         if(n==2)
         {
         	long long A=0;
         	for(int i=1;i<=ans;i++)
         	 for(int j=1;j<=ans;j++)
         	 {
     	     	A=max(A,dp[0][i][j]);
     	     }
     	     cout<<A<<endl;
    		  return 0; 
         }
        for(int i=3;i<=n;i++)
        {
        	for(int j=1;j<=ans;j++)
        	{
            	if(fit(j,i))
            	{
            		for(int k=1;k<=ans;k++)
                    { 
                        if(!(state[j]&state[k]))
                        if(fit(k,i-1))
                         for(int x=1;x<=ans;x++)
                         if(!(state[k]&state[x]))
                         if(!(state[j]&state[x]))
                          if(fit(x,i-2))
                          {
                          	 if(!(state[x]&state[k]))
                             dp[i%2][j][k]=max(dp[i%2][j][k],dp[(i-1)%2][k][x]+num[j]);		
                          }
                    } 
            	}
            	
            }
        }
        
        long long sum=0;
        for(int i=1;i<=ans;i++)
        {
        	for(int j=1;j<=ans;j++)
        	sum=max(sum,dp[n%2][i][j]);
        }
        cout<<sum<<endl;
    }
    
    

    入门剩余题:

    UESTC 数据结构专题一道状压DP

    洛谷— —过河:扩展欧几里得+离散化(有点难)

    展开全文
  • 本次博客,主要是给学弟学妹们讲解一下状压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入门

    2020-08-01 15:01:35
    解题思路:用二进制枚举+dp g[i]表示状态为i时当前背包剩余的体积 f[i]表示状态为i时所用最少的背包数 代码如下: #include<bits/stdc++.h> using namespace std; const int N=20; const int M=1<<18+5;...

    题目一链接
    题目意思就是:给出n个物品,体积为w[i],现把其分成若干组,要求每组总体积<=W,问最小分组。(n<=18)

    解题思路:用二进制枚举+dp

    g[i]表示状态为i时当前背包剩余的体积
    f[i]表示状态为i时所用最少的背包数
    代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    const int N=20;
    const int M=1<<18+5;
    int n,m,a[N],f[M],g[M];
    int main(){
        cin>>n>>m;
        int op=(1<<n);
        for(int i=0;i<n;i++)
            cin>>a[i];
        memset(f,0x3f,sizeof(f));
        f[0]=1; g[0]=m;
        for(int i=0;i<op;i++){//枚举所有的情况
            for(int j=0;j<n;j++){//选择第几个物品
                if((1<<j) & i) continue;//物体已经被选了 
                if(g[i]>=a[j]  && f[i|(1<<j)]>=f[i]){ //物体可以放进  
                //i|(1<<j)指的是当前枚举的情况加上当前选的物品
                   f[i|(1<<j)]=f[i];
                   g[i|(1<<j)]=max(g[i|(1<<j)],g[i]-a[j]);
                }
                else if(g[i]<a[j] && f[i|(1<<j)]>=f[i]+1){ //包放不下了 
                   f[i|(1<<j)]=f[i]+1;
                   g[i|(1<<j)]=max(g[i|(1<<j)],m-a[j]);            
                }
            }
        }    
        printf("%d",f[(1<<n)-1]); 
        return 0;
    }
    

    题二

    给定一个n*m的矩阵(n,m<=20),1表示这个格子能选,0表示这个格子不能选,你需要选出尽可能多的格子,且保证选出来的所有格子直接不相邻(没有公共边)

    例如

    输入
    n=2,m=3
    1 1 1
    0 1 0
    输出

    3

    思路:用二进制枚举+状压dp
    这一行的状态为now,下一行的状态为prev,只要
    (now & prev)== 0 就行了
    此外,我们还需要判断当前行是否合法,只要
    (now | flag)== flag 即可

    #include<bits/stdc++.h>
     
    using namespace std;
     
    const int MAX_N = 20;
    const int MAX_M = 20;
    int state[MAX_N + 1];
    int dp[MAX_N + 1][1 << MAX_M];
     
    bool not_intersect(int now, int prev) {
        return (now & prev) == 0;
    }
     
    bool fit(int now, int flag) {
        return (now | flag) == flag;
    }
    bool ok(int x) {
        // 行内自己是否相交
        return (x & (x / 2)) == 0;      //说明没有相邻的点
    }
    int count(int now) {
        int s = 0;  // 统计 now 的二进制形式中有多少个 1
        while (now) {
            s += (now & 1);  // 判断 now 二进制的最后一位是否为 1,如果是则累加
            now >>= 1;  // now 右移一位
        }
        return s;
    }
     
    int main() {
        int n, m;
        cin >> n >> m;
        // 初始化所有数组
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < m; ++j) {
                int flag;
                cin >> flag;
                state[i] |= (1 << j) * flag;  // 将 (i,j) 格子的状态放入 state[i] 中,state[i] 表示第 i 行的可选格子组成的集合
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < (1 << m); ++j) {  // 枚举当前行的状态
                if (!ok(j) || !fit(j, state[i])) {  // 如果当前行状态不合法则不执行后面的枚举
                    continue;
                }
                int cnt = count(j);  // 统计当前行一共选了多少个格子
                for (int k = 0; k < (1 << m); ++k) {
                    if (ok(k) && fit(k, state[i - 1]) && not_intersect(j, k)) {  // 判断前一行是否合法和当前行和前一行的方案是否冲突
                        dp[i][j] = max(dp[i][j], dp[i - 1][k] + cnt);  // 更新当前行、当前状态的最优解
                    }
                }
            }
        }
        int ans = 0;  // 保存最终答案
        for (int i = 0; i < (1 << m); ++i) {
            ans = max(ans, dp[n][i]);  // 枚举所有状态,更新最大值
        }
        cout << ans << endl;
        return 0;
    }
     
     
    
    展开全文
  • 入门_状压DP

    2020-10-08 21:36:11
    题目描述: 在电影《金陵十三钗》中有十二个秦淮河的女人要自我牺牲代替十二个女学生去赴日本人的死亡宴会。为了不让日本人发现,自然需要一番乔装打扮。但由于天生材质的原因,每个人和每个人之间的相似度是不同的...
  • |算法讨论|状压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次),所以首先应掌握位运算。 到目前为止...
  • Codeforces 1051D Bicolorings 简单状压dp

    万次阅读 2018-09-26 13:40:54
    可以作为状压dp入门题. 由于连通块构成需要相邻,只有上一列的两个格子的颜色对这一列构成连通块的个数有影响. 两个格子的颜色的情况只有4种可能,可以状压这两个格子的涂色方法. 用dp[i][j][k]表示当前涂到iii列,有...
  • 女友ACM训练计划

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

    千次阅读 2017-10-09 16:31:10
    前言没有前言 T1 Hie with the Pie 题意 解析 代码 提示 出处 T2 Doing Homework 题意 解析 代码 提示 出处 T3 Card Collector ... 给你几个点,每个点都有到其他点的价值,请问遍历所有点的最小价值. ... 最短
  • 旅行商问题 & TSP问题:有n个城市,从起点 0 开始游历每一个城市,只访问每个城市一次,最后回到起点,所需要的最短路径是多少? 这个属于NP完全问题。最直接的方法就是枚举法,解空间为n个元素的所有排列组合,为...
  • Hrbust 题目列表【700题】-个人整理

    千次阅读 多人点赞 2016-08-20 17:05:22
    1004、【入门】数塔dp 1005、【思维】序列定和 1006、【进阶】二分查找、好题 1007、【新手】A-B 1008、【新手】水题 1009、【新手】水题 1010、【新手】水题 1011、【新手】水题 1012、【入门】广搜 1015、【新手】...
  • 简单DP入门基础知识

    千次阅读 2018-07-16 15:34:21
    动态规划:DP:Dynamic Programming是算法的设计方法,是一种编程思想,主要用于解决最优解类型的问题。对于一个DP问题,首先将问题分解,任选一个最优解的子状态分析,与原问题(原状态)有什么关系。列出状态转移...
  • ACM动态规划总结(by utobe67)

    千次阅读 多人点赞 2015-05-14 20:50:17
    动态规划一直是ACM竞赛中的重点, 也是难点(对于我这种水平),因为该算法时间效率高,代码量少,多元性强、灵活度高,主要考察思维能力、建模抽象能力。学了这么久动态规划,虽然还只是个菜菜= =,但还是想总结...
  • 状压DP(涉及位运算)

    千次阅读 2018-08-03 18:37:45
    知识点系列之---状压DP
  • 暑假集训总结

    千次阅读 2016-08-29 21:52:01
    结束了为期1个月的暑假集训,在这认识了很多小伙伴,也学了很多知识,很充实的一个暑假。 只是DD太爱睡懒觉了,以至于第2天集训的时候被费老骂了一顿,说 你们俩个以后... 这个月一直死磕dp了。 第一个周~ 学了状
  • 思路:状压DP入门题,这题的子问题其实是每个点的使用状况,这种集合类的DP一般都是状压DP,所以我们用dp[i][j]表示当前在第i个点的时候,所有的点的使用状况,先枚举状态,然后枚举当前的点,再在剩下的点中枚举...
  • 状态压缩DP …看了一个很好的入门介绍
  • A.状态压缩Dp.求拓扑排序可行序列方案数.我们已知如果靠后的节点已经分配完位子了的话,那么其父亲节点也一定完成...经典入门区间Dp.做了很长时间,但是收获很大。 直接设定Dp【i】【j】表示区间【i,j】将A串变成B串
  • 我要开状压dp的坑了。。直播从入门到放弃系列。。那就先拿一道状压dp的水题练练手吧。。然后就找到了这一道。。这道题使我清醒地认识到阻碍我的不是算法,而是视力= =传送门: poj:...
1 2 3 4 5 ... 20
收藏数 789
精华内容 315
热门标签
关键字:

状压dp入门