USACO Training Section 2.2 Subset Sums

英語の原題  
中国語の翻訳  
テーマ:
Nを与え、集合{i|1<=i<=N}を2つの要素と等しいサブセットに分割するスキームの個数を求める.例えば,N=3の場合,{1,2}{3}は1つの解を共有する.
1−Nの数の和が(N+1)N/2であれば,この数が奇数であれば,必ず解がない.偶数であれば,必ず解を構築できる.
直接暴力で解くと、検索空間は(n/2)と大まかに推定されます!でも素早く枝を切ることができます.キーは、最大数から検索を開始し、既定の和が得られるまで、検索されていない最大数を1つ増加するたびに、または和を超えると枝を切ります.例えば、N=7、(7+1)*7/4=14、すなわち、各集合の和は14である.最大数7は必然的にある集合の中で、この数は検索しない.6から1を得ることができます.5から始まります.4から3を取得し、2,1を検索し続けます.3から、検索する必要はありません.3から最大(3+1)*2/2=6<7が得られるからです.

/*
ID: blackco3
TASK: subset
LANG: C++
*/
#include <iostream>
using namespace std;
int n_part=0 ;
void get_subset( int cur_num , int remain ) {
	if( remain<=0 )
		n_part += (remain==0);
	else 
		for( int i=min(cur_num-1,remain); remain<=((i*(i+1))>>1) && i>=1; i-- )
			get_subset( i, remain-i );
}

int main() {	
	freopen("subset.in", "r", stdin);
	freopen("subset.out", "w", stdout);	
	int num ;
	cin >> num ;
	int part_sum = (num * (num + 1) ) >> 1 ;
	if( part_sum & 1 ){
		cout << 0 << endl ;
		return 0 ;
	}
	get_subset(num, (part_sum>>1)-num );
	cout << n_part << endl ;
	return 0;
}

このように探索は5番目の試験点(36)でタイムアウト(NOCOWでいう4番目の点31よりタイムアウトしたほうがいい、ほほほ)であり、試験全体の長さは39であるため、別の方法が必要である.n=8を印刷したときの検索結果は以下の通りです.
8 7 3
8 7 2 1
8 6 4
8 6 3 1
8 5 4 1
8 5 3 2
8 4 3 2 1
yu'xyu'xiyu'xiaの残数が3の場合、2つのスキーム3,21があることに注意してください.この繰返しスキームは,探索全体が指数関数的に複雑になる.このような繰り返しサブ問題を持つ解に対しては,自然に動的計画が考えられるはずであり,a[i][j]=i以下の数でjの個数を求める.自然とa[i][j]=a[i-1][j-i]+a[i-1][j](i-1を選択するか否かを示す)がある.以前の解析と結びつけて,a[N][(N+1]*N/4]が答えであるとともに,この表に基づいてすべての解を再構成することができる.
スレッドには1次元DPを用いたものがあり,実際には上述した2次元DPを線形化している.

/*
ID: blackco3
TASK: subset
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
#define _max_ 40

int main() {	
	freopen("subset.in", "r", stdin);
	freopen("subset.out", "w", stdout);	
	int num ;
	cin >> num ;
	int part_sum = (num * (num + 1) ) >> 1 ;
	if( part_sum & 1 ){
		cout << 0 << endl ;
		return 0 ;
	}
	part_sum = part_sum>>1 ;
	int sum_num[_max_][((_max_*(_max_+1))>>2)+1] ;
	memset(sum_num, 0, sizeof(sum_num));
	sum_num[1][1]=1 ;
	for( int i=2; i<=num; i++ ){
		for(int j=1; j<=part_sum; j++ ){
			sum_num[i][j] += i-1>=1 ? sum_num[i-1][j] + ( j-i>=1 ? sum_num[i-1][j-i] : 0 ) : 0 ;
		}
	}
	cout << sum_num[num][part_sum] << endl ;
	return 0;
}

PS:解の初めはNに直接DPをしたいと思っていましたが、半日データを調べても実行可能な適切な案が見つかりませんでした.