学步园

大意：要求把一些物品放入背包，使得剩下的背包都放不下。

思路：

首先考虑所有可行方案，状态转移方程是： f[v] += f[v-V[i]];

如果考虑“使剩下的物品都放不下”的条件，如果剩下的体积最小为v，那么方案数就是sum{f[j]}(C >= j > C-v)，这个很好理解，只有剩余背包量在上述范围内才有可能放不进体积为v的物品。

怎么实现呢？首先对体积进行一下预排序，然后枚举i作为剩余体积中最小的一件。而且对所有的v < V[i]的背包必须都要放入背包，对于i不能放入背包，对于v > V[i]的物品进行0/1背包统计方案，将所有sum{f[j]}(C >= j > C-v)累加到ans。

由于每次需要对n-i件物品做统计，一共是n次，时间复杂度是O(n^2*C)。

注意几个小细节。

1、即初始值f[sum] = 1，sum为前i-1个物品的体积和，为什么呢？我的理解是原来的起点由f[0]已经变为f[sum]了，因为前i-1件物品必须放入背包。

2、由于起点变了，所以递推时的递推边界也变成 for(v = C; v >= V[i]+sum; v--)。

3、最后累加时，注意合法边界是k >= sum，因为小于sum的背包值实际上是没有意义的。

4、超INT，用unsigned long long 。

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

typedef unsigned long long ULL;

const int MAXN = 1010;

ULL f[MAXN];
ULL V[MAXN];
int times;

ULL n, C;

void init()
{
	memset(f, 0, sizeof(f));
}

void dp()
{
	ULL ans = 0, sum = 0;
	for(ULL i = 1; i <= n; i++)
	{
		init();
		f[sum] = 1;
		for(ULL j = i+1; j <= n; j++)
		{
			for(ULL v = C; v >= V[j]+sum; v--)
			{
				f[v] += f[v-V[j]];
			}
		}
		for(ULL k = C; k >= C-V[i]+1; k--) if(k >= sum)
		{
			ans += f[k];
		}
		sum += V[i];
	}
	printf("%llu\n", ans);
}

void read_case()
{
	scanf("%llu%llu", &n, &C);
	for(ULL i = 1; i <= n; i++) scanf("%llu", &V[i]);
}

void solve()
{
	read_case();
	sort(V+1, V+n+1);
	printf("%d ", ++times);
	dp();
}

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