蒙德里安的梦想

求把长宽分别为N,M的棋盘分割成若干个1*2的的长方形，有多少种方案。

输入格式
输入包含多组测试用例。

每组测试用例占一行，包含两个整数N和M。

当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。

输出格式
每个测试用例输出一个结果，每个结果占一行。

数据范围
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

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
using namespace std;

typedef long long LL;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
bool st[M];//存储每一列上合法的摆放状态

//f[i][j]表示摆放第i列,第i-1列向后伸出来的方格状态为j的方案数,用01表示是否戳出来

int main()
{
    while (scanf("%d%d", &n, &m))
    {
        if (n == 0 && m == 0)
            return 0;

        memset(f, 0, sizeof f);//初始化,重新计算

        /*枚举合法状态*/
        for (int i = 0; i < 1 << n; i++)//一共n行,枚举n位不同的状态
        {
            int cnt = 0;//连续0的个数
            st[i] = true;
            for (int j = 0; j < n; j++)//左移的位数
            {     
                if (i >> j & 1)//判断当前这一位是否1
                {
                    if (cnt & 1)//判断当前连续0的个数是否是奇数
                        st[i] = false;
                }
                else
                    cnt++;
            }
            if (cnt & 1)//最后一段连续0的个数
                st[i] = false;
        }

        /*dp过程*/
        f[0][0] = 1;
        for (int i = 1; i <= m; i++)//枚举列数
            for (int j = 0; j < 1 << n; j++)//i列的状态
                for (int k = 0; k < 1 << n; k++)//i-1列的状态
                    if ((j & k) == 0 && st[j | k])//前后两列不冲突,并且不存在连续奇数个0
                        f[i][j] += f[i - 1][k];

        cout << f[m][0] << endl;//从m-1列伸出,并且m列状态是0的方案数
    }
    return 0;
}

最短Hamilton路径

给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数n。

接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（记为a[i,j]）。

对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

输出格式
输出一个整数，表示最短Hamilton路径的长度。

数据范围
1≤n≤20
0≤a[i,j]≤10^7

输入样例

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

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
using namespace std;

typedef long long LL;
const int N = 20, M = 1 << N;
int n;
int w[N][N];//权重
int f[M][N];

//f[i][j]表示当前移动到j,已经走过点的集合为i

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <n; j++)
            scanf("%d", &w[i][j]);

    memset(f, 0x3f, sizeof f);//初始化
    f[1][0] = 0;//起点

    for (int i = 0; i < 1 << n; i++)//表示所有的情况
        for (int j = 0; j < n; j++)//j表示走到哪一个点
            if (i >> j & 1)//i一定要包含j
                for (int k = 0; k < n; k++)//走到j之前,以k为终点的最短距离
                    if ((i - (1 << j)) >> k & 1)//i状态除去j点
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

    cout << f[(1 << n) - 1][n - 1];//终点是n-1的点的最短距离
    return 0;
}