題意：
? ? ? 給你兩個數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个数的和是平方数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。