首页 > 代码库 > 7.4 魔术球问题弱化版

7.4 魔术球问题弱化版

题目描述

假设有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,2,3,…的球。

(1)每次只能在某根柱子的最上面放球。

(2)在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 n 根柱子上最多能放多少个球。例如,在 4 根柱子上最多可放 11 个

对于给定的 n,计算在 n 根柱子上最多能放多少个球。

输入描述

第 1 行有 1 个正整数 n,表示柱子数。

输出描述

一行表示可以放的最大球数

4

样例输出。

样例输入

11

题目限制(为什么说弱化版就在这里)

N<=60,时限为3s;比起原题还有弱化在不用打出方案,方案太坑了

 

本题为一个网络流问题的弱化版,结果弱化成模拟了。。。

所以,就直接按模拟做吧,用了一点小技巧:

1.贪心,尽可能多地让球都叠加在一个柱子上,毕竟,即使一个数没有能与它组成平方数,他还可以独占一个柱子

2.既然只是相邻组成平方数,那就没必要考虑下面的球的编号,只需储存最上面球的编号即可判断某个球能否放在这根柱子上

 

 

 

#include<cstdio>
int n,i,t=1,book=1;
int s[105];
int pd(int x)
{
  for(int j=1;j*j<=x;j++)
  {
    if(j*j==x) return 1;
  }
  return 0;
}
int main()
{
  scanf("%d",&n);
  while(book==1)
  {
    book=0;
    for(i=1;i<=n;i++)
    {
     if(pd(t+s[i])==1)
      {
        s[i]=t;
        t++;
        book=1;
        break;
      }
      if(s[i]==0)
      {
        s[i]=t;
        t++;
        book=1;
        break;
      }
    }
  }
  printf("%d",t-1);
  return 0;
}

7.4 魔术球问题弱化版