题意: 给你一堆数字,一个上限,让你找出有一定特征的组合个数,这些组合的特点是对于每一个组合,如果加入任何一个组合外的数字,和就会超过上限. 思路:先从小到大排序,对于第一个数字, 不选它:对后面的数字跑朴素01背包,跑完后在[d-arr[pos]+1,d]内的组合个数都是满足要求的, 选它:用上限d减去这个数字,剩下的数字与新的上限继续按照这个逻辑算下去.
代码:
#include <algorithm> #include <iostream> #include <cstdio> #include <stack> #include <vector> #include <string> #include <cstring> #include <cmath> #include <queue> #include <set> #include <map> #include <list> #include <ctime> using namespace std; #define ll long long #define ld long double #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define EXP 1e-8 #define MOD 1000000007 #define N 50005 #define random(x) rand()%x+1 inline ll next_ll() { char c; while(c = getchar(), c < '0' || c > '9'); ll r = c-'0'; while(c = getchar(), c >= '0' && c <= '9') r = r*10+c-'0'; return r; } ll n, v, d; ll dp[5000]; ll arr[100]; int main() { #ifdef Wang_Zhifeng freopen("in.txt", "r", stdin); #endif scanf("%lld", &n); for(ll cnt = 1; cnt <= n; ++cnt) { dp[0] = 1; scanf("%lld%lld", &v, &d); for(ll i = 0; i < v; ++i) { scanf("%lld", &arr[i]); } if(v==1) { printf("%lld %d\n", cnt, arr[0] <= d ? 1 : 0); continue; } sort(arr, arr+v); ll ans = 0; for(ll pos = 0; pos < v; ++pos) { if(d < arr[pos]) { if(pos!=0)ans++; break; } if(d==arr[pos]) { for(int i = pos; i < v; ++i) { if(arr[i]==arr[pos]) { ans++; } else { break; } } break; } memset(dp, 0, sizeof(dp)); dp[0] = 1; for(ll i = pos+1; i < v; ++i) { for(ll j = d; j >= arr[i]; --j) { dp[j] += dp[j-arr[i]]; } } for(ll i = d-arr[pos]+1; i <= d; ++i) { ans += dp[i]; } d -= arr[pos]; } printf("%lld %lld\n", cnt, ans); } return 0; }