汉诺塔（四）

时间限制：

3000 ms  |  内存限制：65535 KB

难度：

2

 

描述

    汉诺塔问题是一个经典的问题，现在我们有 n 个柱子和 m 个编号（1～m）的球，我们现在要求把尽量多的球放在尽量少的柱子上，如果相邻两个球的和不是完全平方数的话球会相互排斥而无法接触。(注意：球必须从小到大放，每次只能放在其他球的上面或者一个新的柱子上面)

 

输入

首先一个T，表示T组测试数据，然后一个n（1<=n<=50）.

输出

输出一行，表示n个柱子能放的最大的球编号。

样例输入

14

样例输出

11 题解：暴力 代码：

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int INF=0x3f3f3f3f;#define mem(x,y) memset(x,y,sizeof(x))#define SI(x) scanf("%d",&x)#define SL(x) scanf("%lld",&x)#define PI(x) printf("%d",x)#define PL(x) printf("%lld",x)#define P_ printf(" ")#define T_T while(T--)const int MAXN=2010;bool c[MAXN];int T;int main(){ SI(T); int n; T_T{ SI(n); mem(c,false); int cur; set
             
              st; for(int i=1;i<=100;i++)st.insert(i*i); int cnt=n+1; int ans; for(int i=1;i