#include <iostream>
using namespace std;

int V,D,d[31],sum[31];
unsigned int dp[31][1001];
void work()
{
   memset(dp,0,sizeof(dp));
   for(int i=1;i<=V;i++)
   {
	   for(int j=1;j<=D;j++)
	   {
		   if( j>= sum[i] )
			   dp[i][j] = 1;
		   else 
		   {
			   if( j>= d[i] )
			   {
				   if( dp[i-1][j-d[i]] >0 )
				       dp[i][j] = dp[i-1][j-d[i]] + dp[i-1][j];
				   else 
			           dp[i][j] = 1 + dp[i-1][j];
               }
			   else
				   dp[i][j] = dp[i-1][j];
		   }
	   }
   }
}

int main()
{
    freopen("C:\\ACMData.txt","r",stdin);
	int T,i,k=1; scanf("%d",&T);
	while(T)
	{
	    scanf("%d%d",&V,&D);
		for(i=1;i<=V;i++) scanf("%d", &d[i]);
        sum[0] =0;
		for(i=1;i<=V;i++) sum[i] = sum[i-1] + d[i];
        work(); printf("%d %u\n",k++,dp[V][D]);

		T--;
	}
    return 0;
}
 

• 先对a[]排序 (949) qywyh_scut 2007-04-20 17:40:17