中南林业大学校赛I背包问题(折半枚举||01背包递归写法)

#include
#define LL long long
#define ULL unsigned long long#define scs(i) scanf("%s", i)
#define sci(i) scanf("%d", &i)
#define scd(i) scanf("%lf", &i)
#define scl(i) scanf("%lld", &i)
#define scIl(i) scanf("%I64d", &i)
#define scii(i, j) scanf("%d %d", &i, &j)
#define scdd(i, j) scanf("%lf %lf", &i, &j)
#define scll(i, j) scanf("%lld %lld", &i, &j)
#define scIll(i, j) scanf("%I64d %I64d", &i, &j)
#define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k)
#define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k)
#define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k)
#define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k)#define lson l, m, rt<<1
#define rson m&＃43;1, r, rt<<1|1
#define lowbit(i) (i & (-i))
#define mem(i, j) memset(i, j, sizeof(i))#define fir first
#define sec second
#define ins(i) insert(i)
#define pb(i) push_back(i)
#define pii pair
#define mk(i, j) make_pair(i, j)
#define all(i) i.begin(), i.end()
#define pll pair
using namespace std;
int v[35];int DP(int n, int m)
{if(n <0 || m <0) return 0;if(n &＃61;&＃61; 0 || m &＃61;&＃61; 0) return 1;return DP(n-1, m-v[n]) &＃43; DP(n-1, m);
}int main(void)
{int n;while(~sci(n)){int m;sci(m);for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) sci(v[i]);printf("%d\n", DP(n, m));}return 0;
}

#include
#define LL long long
#define ULL unsigned long long#define scs(i) scanf("%s", i)
#define sci(i) scanf("%d", &i)
#define scd(i) scanf("%lf", &i)
#define scl(i) scanf("%lld", &i)
#define scIl(i) scanf("%I64d", &i)
#define scii(i, j) scanf("%d %d", &i, &j)
#define scdd(i, j) scanf("%lf %lf", &i, &j)
#define scll(i, j) scanf("%lld %lld", &i, &j)
#define scIll(i, j) scanf("%I64d %I64d", &i, &j)
#define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k)
#define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k)
#define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k)
#define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k)#define lson l, m, rt<<1
#define rson m&＃43;1, r, rt<<1|1
#define lowbit(i) (i & (-i))
#define mem(i, j) memset(i, j, sizeof(i))#define fir first
#define sec second
#define ins(i) insert(i)
#define all(i) i.begin(), i.end()
#define pb(i) push_back(i)
#define pii pair
#define mk(i, j) make_pair(i, j)
#define pll pair
using namespace std;
const int maxn &＃61; 30 &＃43; 2;
int n;
LL m, v[maxn];
vector arr;int main(void)
{while(cin>>n>>m){arr.clear();for(int i&＃61;0; i) scl(v[i]);for(int i&＃61;0; i<(1<<(n/2)); i&＃43;&＃43;){LL sum &＃61; 0;for(int j&＃61;0; j2; j&＃43;&＃43;)if((i & (1<<j)))sum &＃43;&＃61; v[j];arr.pb(sum);}sort(all(arr));int ans &＃61; 0;for(int i&＃61;0; i<(1<<(n-n/2)); i&＃43;&＃43;){LL sum &＃61; 0;for(int j&＃61;0; j<(n-n/2); j&＃43;&＃43;)if((i & (1<<j)))sum &＃43;&＃61; v[j&＃43;n/2];ans &＃43;&＃61; upper_bound(all(arr), m-sum) - arr.begin();}cout<endl;}return 0;
}