超级汉诺塔

Question

Description
在YYHS有一种奇异的汉诺塔，在汉诺塔中存放的圆盘式上大下小的，且在同一塔上的相邻两个圆盘大小之和，恰为一个质数，现有N根汉诺塔，问最多能将大小从1开始连续的圆盘放入这N个汉诺塔中。注意放入的顺序必须是从1，N。

Input
一个整数N(1<=N<=15).
Output
输出最多能放的圆盘数目。
Sample Input
2
Sample Output
7

样例解释：
4
3 7
2 6
1 5
当N=2 塔中数最多可以填到7

下边是解释

4
3 7
2 6
1 5

因为N=2 所以又两个塔，，，塔中上下两数之和是质数，，，问当
1<=n<=15的所有答案,,,,,或公式

Answer 1

现在怎么信息学的题目也拿到数学版来问了..
言归正传，这个题注意到两点:
1.如果N是所求的最大值，那么N-1,N-2...1个盘子也能放到那些汉诺塔上，换言之就是存在单调性
2.构造一个顶点数位N的有向图G[i][j](1<=i<=N,1<=j<=N),i和j连一条边当且仅当i<j并且i+j为质数，题目实质要求图的最小路径覆盖
得到具体算法:
1.二分N,N上界取800,下界取1
2.对G[i][j]求最大二分匹配M,判断N-M是否小于等于汉诺塔数，若满足则更新下界，否则更新上界
程序时间复杂度O(800*800*log800),空间复杂度O(800*800)是可以接受的
因为不知道你用pascal还是C,只给你每个N的答案好了:
1:4
2:7
3:43
4:60
5:61
6:62
7:172
8:269
9:452
10:573
11:674
12:675
13:676
14:677
15:678

参考资料：一个老ACMer的建议