学步园

传送门：【HDU】5000 Clone

题目分析：首先所有方案中各位的和都等于一个数x，然后这个x取到T[ i ]之和的二分之一时答案最大。

运气很好，蒙出来的。。。最后时刻AC。。。

有重复计算，所以可以用到记忆化搜索。

代码如下：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )

const int MAXN = 1005 ;
const int mod = 1e9 + 7 ;

int T[MAXN << 1] ;
int dp[MAXN << 1][MAXN] ;
bool vis[MAXN << 1][MAXN] ;
int n ;

void dfs ( int cur , int sum ) {
	vis[cur][sum] = 1 ;
	if ( cur == n ) {
		if ( T[n] < sum ) dp[cur][sum] = 0 ;
		else dp[cur][sum] = 1 ;
		return ;
	}
	dp[cur][sum] = 0 ;
	int tmp = min ( sum , T[cur] ) ;
	FOR ( i , 0 , tmp ) {
		if ( !vis[cur + 1][sum - i] ) dfs ( cur + 1 , sum - i ) ;
		dp[cur][sum] += dp[cur + 1][sum - i] ;
		if ( dp[cur][sum] >= mod ) dp[cur][sum] -= mod ;
	}
}

void solve () {
	int sum = 0 ;
	scanf ( "%d" , &n ) ;
	FOR ( i , 1 , n ) {
		scanf ( "%d" , &T[i] ) ;
		sum += T[i] ;
	}
	sort ( T + 1 , T + n + 1 ) ;
	sum >>= 1 ;
	FOR ( i , 0 , sum ) CLR ( vis[i] , 0 ) ;
	dfs ( 1 , sum ) ;
	printf ( "%d\n" , dp[1][sum] ) ;
}

int main () {
	int T ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) solve () ;
	return 0 ;
}