P1466 集合 Subset Sums

• ?
• 162通過
• 308提交
• 題目提供者該用戶不存在
• 標(biāo)簽USACO
• 難度普及/提高-

?提交??討論??題解??

最新討論

• 暫時(shí)沒有討論

題目描述

對(duì)于從1到N (1 <= N <= 39) 的連續(xù)整數(shù)集合，能劃分成兩個(gè)子集合，且保證每個(gè)集合的數(shù)字和是相等的。舉個(gè)例子，如果N=3，對(duì)于{1，2，3}能劃分成兩個(gè)子集合，每個(gè)子集合的所有數(shù)字和是相等的：

{3} 和 {1,2}

這是唯一一種分法（交換集合位置被認(rèn)為是同一種劃分方案，因此不會(huì)增加劃分方案總數(shù)） 如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分法的子集合各數(shù)字和是相等的:

{1,6,7} 和 {2,3,4,5} {注 1+6+7=2+3+4+5}

{2,5,7} 和 {1,3,4,6}

{3,4,7} 和 {1,2,5,6}

{1,2,4,7} 和 {3,5,6}

給出N，你的程序應(yīng)該輸出劃分方案總數(shù)，如果不存在這樣的劃分方案，則輸出0。程序不能預(yù)存結(jié)果直接輸出（不能打表）。

輸入輸出格式

輸入格式：

輸入文件只有一行，且只有一個(gè)整數(shù)N

輸出格式：

輸出劃分方案總數(shù)，如果不存在則輸出0。

輸入輸出樣例

輸入樣例#1：

7

輸出樣例#1：

4

說明

翻譯來自NOCOW

USACO 2.2

分析：這道題數(shù)據(jù)小，很容易過，每個(gè)數(shù)要么在第一個(gè)集合，要么在第二個(gè)集合，那么暴搜可以解決，在這里講一個(gè)比較高級(jí)一點(diǎn)的做法，其實(shí)我們可以把兩個(gè)集合看作取不取這個(gè)數(shù)，那么這道題就變成了0-1背包問題，設(shè)f[i][j]為前i個(gè)數(shù)中讓和為j的方案?jìng)€(gè)數(shù)，可以發(fā)現(xiàn)方案數(shù)=不取i的方案數(shù)+取i的方案數(shù)，前提是能夠取i,即j > i,注意：如果選了一個(gè)數(shù)，那么方案數(shù)是不變的，所以狀態(tài)轉(zhuǎn)移方程為f[i][j] = f[i-1][j] + f[i-1][j - i] (j > i).然后發(fā)現(xiàn)方案數(shù)如果位置不同那么還是算同一個(gè)方案，那么問題就是求用n個(gè)數(shù)湊num/2的方案數(shù)(num是和)，當(dāng)然，如果num為奇數(shù)則無解.

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;int n,num,f[40][800];int main() {scanf("%d", &n);num = n * (n + 1) / 2;if (num % 2)printf("0\n");else{f[1][0] = 1;f[1][1] = 1;for (int i = 2; i <= n; i++)for (int j = 0; j <= num; j++)if (j > i)f[i][j] = f[i - 1][j] + f[i - 1][j - i];elsef[i][j] = f[i - 1][j];printf("%d\n", f[n][num / 2]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zbtrs/p/5918068.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P1466 集合 Subset Sums的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。