hdu4982 暴搜+剪枝（k个数和是n，k-1个数的和是平方数）

题意：

给你两个数n,k问你是否怎在这样一个序列：

（1）这个序列有k个正整数，且不重复.

（2）这k个数的和是n.

（3）其中有k-1个数的和是一个平方数.

思路：

直接暴搜，一开始剪枝没写好，TLE了几次。这个题目我们可以枚举所有小于n的平方数，然后搜索去构造，用k-1个数构造出来当前的这个平方数，同时自己还写了几个小枝.

a:求了一个枚举的下界，那就是1+2+3+...+ k-1,上界是n。

b:对于每一次，枚举深搜的时候的最大数 = 当前枚举数 i -（1+2+..+k-2）

c:深搜的时候，因为枚举是越来越大的，那么如果当前的和sum,剩余的枚举个数（k-1-s）,剩下的全是连续的，那么剩下的数的平均数是当前数now加上（k-1-s）/ 2,如果当前的和加上剩下的数的最小和大于当前枚举的平方数，那么当前状态失败，表示是

if(sum + (k - 1 - s) * (now + (k - 1 - s) / 2) > nowsum) return.

#include<stdio.h>

#include<string.h>



int mark[222222];

int n ,k ,ok ,nowsum ,max ,nowmk;

void DFS(int now ,int s ,int sum)

{

   if(s == k - 1)

   {

      if(sum == nowsum) ok = 1;

      return;

   }

   if(sum + (k - 1 - s) * (now + (k - 1 - s) / 2) > nowsum) return;

   for(int i = now + 1 ;i <= max && !ok;i ++)

   if(i != nowmk) DFS(i ,s + 1 ,sum + i);

}

int main ()

{

    memset(mark ,0 ,sizeof(mark));

    for(int i = 1 ;1 ;i ++)

    {

        int tmp = i * i;

        if(tmp > 200000) break;

        mark[tmp] = 1;

    }

    while(~scanf("%d %d" ,&n ,&k))

    {

        int min = 0;

        for(int i = 1 ;i <= k - 1 ;i ++)

        min += i;

        ok = 0;

        for(int i = n - 1 ;i >= min && !ok;i --)

        {

            if(!mark[i]) continue;

            nowmk = n - i;

            max = 0;

            for(int j = 1 ;j < k - 1 ;j ++)

            max += j;

            max = i - max;

            nowsum = i;

            DFS(0 ,0 ,0);

         }

         if(ok) printf("YES\n");

         else printf("NO\n");

      }

      return 0;

}

巴特西

hdu4982 暴搜+剪枝（k个数和是n，k-1个数的和是平方数）

最新文章

热门文章