一、AcWing 291. 蒙德里安的梦想
(1)问题描述
????????
求把?N×MN×M?的棋盘分割成若干个?1×21×2?的的长方形，有多少种方案。
例如当?N=2，M=4N=2，M=4?时，共有?55?种方案。当?N=2，M=3N=2，M=3?时，共有?33?种方案。
如下图所示：
输入格式
输入包含多组测试用例。
每组测试用例占一行，包含两个整数?NN?和?MM。
当输入用例?N=0，M=0N=0，M=0?时，表示输入终止，且该用例无需处理。
输出格式
每个测试用例输出一个结果，每个结果占一行。
数据范围
1≤N,M≤111≤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(2)代码实现
????????
import java.util.*;
public class Main
{
static Scanner in = new Scanner(System.in);
static int N = 12, M = 1 << N;
static long f[][] = new long[N][M];
static boolean st[] = new boolean[M];
public static void main(String args[])
{
int n, m;
while (true)
{
n = in.nextInt(); m = in.nextInt();
if ((n | m) == 0) break;
for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) f[i][j] = 0;
for (int i = 0; i < 1 << n; i++)
{
st[i] = true;
int cnt = 0;
for (int j = 0; j < n; j++)
if ((i >> j & 1) != 0)
{
if ((cnt & 1) != 0) st[i] = false;
cnt = 0;
}
else cnt++;
if ((cnt & 1) != 0) st[i] = false;
}
f[0][0] = 1;
for (int i = 1; i <= m; i++)
for (int j = 0; j < 1 << n; j++)
for (int k = 0; k < 1 << n; k++)
if ((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
System.out.println(f[m][0]);
}
}
}?二、AcWing 91. 最短Hamilton路径
(1)问题描述
????????
给定一张?nn?个点的带权无向图，点从?0～n?10～n?1?标号，求起点?00?到终点?n?1n?1?的最短 Hamilton 路径。
Hamilton 路径的定义是从?00?到?n?1n?1?不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数?nn。
接下来?nn?行每行?nn?个整数，其中第?ii?行第?jj?个整数表示点?ii?到?jj?的距离（记为?a[i,j]a[i,j]）。
对于任意的?x,y,zx,y,z，数据保证?a[x,x]=0，a[x,y]=a[y,x]a[x,x]=0，a[x,y]=a[y,x]?并且?a[x,y]+a[y,z]≥a[x,z]a[x,y]+a[y,z]≥a[x,z]。
输出格式
输出一个整数，表示最短 Hamilton 路径的长度。
数据范围
1≤n≤201≤n≤20
0≤a[i,j]≤1070≤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(2)代码实现
????????
import java.util.*;
public class Main
{
static Scanner in = new Scanner(System.in);
static int N = 20, M = 1 << N, INF = 0x3f3f3f3f;
static int w[][] = new int[N][N], f[][] = new int[M][N];
public static void main(String args[])
{
for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) f[i][j] = INF;
int n = in.nextInt();
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) w[i][j] = in.nextInt();
f[1][0] = 0;
for (int i = 0; i < 1 << n; i++)
for (int j = 0; j < n; j++)
if ((i >> j & 1) == 1)
for (int k = 0; k < n; k++)
if ((i - (1 << j) >> k & 1) == 1)
f[i][j] = Math.min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
System.out.println(f[(1 << n) - 1][n - 1]);
}
}三、蓝桥杯试题 算法提高 秘密行动
(1)问题描述
?????????
小D接到一项任务，要求他爬到一座n层大厦的顶端与神秘人物会面。这座大厦有一个神奇的特点，每层的高度都不一样，同时，小D也拥有一项特殊能力，可以一次向上跳跃一层或两层，但是这项能力无法连续使用。已知向上1高度消耗的时间为1，跳跃不消耗时间。由于事态紧急，小D想知道他最少需要多少时间到达顶层。
输入格式
第一行包含一个整数n，代表楼的高度。
接下来n行每行一个整数ai，代表i层的楼层高度（ai <= 100）。
输出格式
输出1行，包含一个整数，表示所需的最短时间。
样例输入
5
3
5
1
8
4
样例输出
1
数据规模和约定
对20%的数据,n<=10
对40%的数据,n<=100
对60%的数据,n<=5000
对100%的数据,n<=10000
(2)代码实现
????????
import java.util.*;
public class Main{
static Scanner in=new Scanner(System.in);
static int n,m;
static int[] a=new int[10010];
static int[][] f=new int[10010][2];
public static void main(String[] args){
m=in.nextInt();
for(int i=1;i<=m;i++) a[i]=in.nextInt();
for(int i=0;i< f.length;i++){
for(int j=0;j<f[0].length;j++){
f[i][j]=0;
}
}
f[1][0]=a[1];
f[1][1]=0;
for(int i=2;i<=m;i++)
{
f[i][0]=Math.min(f[i-1][0],f[i-1][1])+a[i];
f[i][1]=Math.min(f[i-1][0],f[i-2][0]);
}
System.out.println(Math.min(f[m][0],f[m][1]));
}
}