南平建设集集团网站,怎样注册公司邮箱账号,ih5制作软件,wordpress外网ip访问不了状压DP
对于数据范围n20的可以考虑状压DP
1.蒙德里安的梦想
题目描述
求把 N M NM NM 的棋盘分割成若干个 12 的的长方形#xff0c;有多少种方案。
例如当$ N2#xff0c;M4$ 时#xff0c;共有 5 种方案。当 N 2 #xff0c; M 3 N2#xff0c;M3 N2…状压DP
对于数据范围n20的可以考虑状压DP
1.蒙德里安的梦想
题目描述
求把 N × M N×M N×M 的棋盘分割成若干个 1×2 的的长方形有多少种方案。
例如当$ N2M4$ 时共有 5 种方案。当 N 2 M 3 N2M3 N2M3 时共有 3 种方案。
如下图所示 输入格式
输入包含多组测试用例。
每组测试用例占一行包含两个整数 N 和 M。
当输入用例 N0M0 时表示输入终止且该用例无需处理。
输出格式
每个测试用例输出一个结果每个结果占一行。
数据范围 1 ≤ N , M ≤ 11 1≤N,M≤11 1≤N,M≤11
输入样例
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0输出样例
1
0
1
2
3
5
144
51205分析
状压DP模板题本题若横着放的长方形确定其他就只能竖着放所以我们只需要考虑横着放的所有状态定义f[i,j]为第i列伸出到第i1列的状态为j的方案数对于状压DP每次假定前一个状态为k则k为第i-1列伸到第i列的状态枚举所有的j和k判断是否符合条件即可
这里的条件是 j和k的每一位不能同时为1否则会出现长度为3的长方形 j k 0 j\k0 jk0 第i列不能出现连续的奇数空这里我们会出现一个问题如何求第i列的状态很容易想道第i列的状态是由第i-1伸到第i列和第i列伸到第i1列共同引起的所以第i列状态为 j ∣ k j|k j∣k对于每一列的状态我们可以预处理一个st数组届时判断 s t [ j ∣ k ] st[j|k] st[j∣k]是否为真即可
代码
#includebits/stdc.h
#define int long long
using namespace std;const int N12,M(111)10;
int dp[N][M];
bool st[M];
void init(int n)
{for(int i0;i1n;i){st[i]true;int cnt0;for(int j0;jn;j){int kij1;if(k){if(cnt1) st[i]false;cnt0;}else cnt;}if(cnt1) st[i]false;}
}
signed main()
{int n,m;while(cinnm){if(n0m0) break;init(n);memset(dp,0,sizeof(dp));dp[0][0]1;for(int i1;im;i){for(int j0;j1n;j){for(int k0;k1n;k){if((kj)0st[k|j]true){dp[i][j]dp[i-1][k];}}}}coutdp[m][0]endl;}return 0;
}2.最短哈密顿距离
题目描述
给定一张 n 个点的带权无向图点从 0 ∼ n − 1 0∼n−1 0∼n−1 标号求起点 0 到终点 n − 1 n−1 n−1的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 0 0 到 n−1不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数 n n n。
接下来 $n $行每行 n n n 个整数其中第 i i i 行第$ j 个整数表示点 个整数表示点 个整数表示点 i$ 到 $j 的距离记为 的距离记为 的距离记为 a[i,j]$。
对于任意的 x , y , z x,y,z x,y,z数据保证 a [ x , x ] 0 a [ x , y ] a [ y , x ] a[x,x]0a[x,y]a[y,x] a[x,x]0a[x,y]a[y,x] 并且$ a[x,y]a[y,z]≥a[x,z]$。
输出格式
输出一个整数表示最短 Hamilton 路径的长度。
数据范围 1 ≤ n ≤ 20 1≤n≤20 1≤n≤20 0 ≤ a [ i , j ] ≤ 1 0 7 0≤a[i,j]≤10^7 0≤a[i,j]≤107
输入样例
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例
18分析
定义 f [ i , j ] f[i,j] f[i,j]为以j为终点通过路径状态压缩后为i的所有方案最终答案是 f [ 1 n − 1 ] [ n − 1 ] f[1n-1][n-1] f[1n−1][n−1]用k表示前一个状态枚举所有的jik判断i内是否包含终点j和前一个点k若包含则 f [ i , j ] M i n ( f [ i , j ] , f [ i − { j } ] [ k ] a [ k , j ] ) f[i,j]Min(f[i,j],f[i-\{j\}][k]a[k,j]) f[i,j]Min(f[i,j],f[i−{j}][k]a[k,j])
代码
#includebits/stdc.h#define int long longusing namespace std;const int N20,M(120)10,infLLONG_MAX/2;int f[M][N];
int a[N][N];
signed main()
{int n;cinn;for(int i0;in;i)for(int j0;jn;j)cina[i][j];int resinf;memset(f,0x3f,sizeof(f));f[1][0]0;int cnt0;for(int j1;jn;j){for(int i0;i1n;i){if(i10) continue;if(ij1){for(int k0;kn;k){if(ik1){f[i][j]min(f[i][j],f[i-(1j)][k]a[k][j]);}}}}}coutf[(1n)-1][n-1]endl;return 0;
}
