HHUOJ 1088 我们遇到什么困难也不要怕

题目描述

我向佛祖许愿，希望群里所有的朋友都不开心

佛说:“不行, 只能四天”

我说:“行, 春天、夏天、秋天、冬天”

佛说:“不行, 只能三天”

我说:“行, 昨天、今天、明天”

佛说:“不行, 只能两天”

我说:“行, 那就白天、黑天(指夜晚)”

佛哭了, 说:“行吧”

于是由于我邪恶的许愿, 群里的1~n位朋友们在明天的白天和夜晚这两个时段中, 必须至少有一个时段不开心. 每个群友都有自己的两个郁闷能量

ai,bi, 分别表示编号为i的群友若在白天不开心和夜晚不开心所收获的郁闷值. 邪恶的我认为, 只有群友们在白天郁闷值的总和与夜晚郁闷值的总和都大等于h, 群友们才是真正的都不开心.

佛茫然地望着你, 请你告诉佛祖有多少种群友不开心的方案能满足这个邪恶许愿?

输入

多组测试样例，第一行一个整数T，表示测试样例组数。0<T<=100

每组测试样例包括三行

第一行为题目中描述的n h, 1<=n<=12, 0<=h<=1,000,000

第二行为n个非负整数, {ai} 意义如题目描述, 0<=ai<=100,000

第三行为n个非负整数, {bi} 意义如题目描述, 0<=bi<=100,000

输出

输出共T行, 每行一个整数, 代表能满足邪恶许愿的方案数.

样例输入

22 31 23 32 52 210 30

样例输出

30

简单的dfs，但是别忘了回溯，/(ㄒoㄒ)/~~

#include<bits/stdc++.h>typedef long long ll;using namespace std;int n,h;int cnt;int sum1,sum2;int a[20][2];void dfs(int x){if(x==n) {if(sum1>=h && sum2>=h)cnt++;return ;}sum1+=a[x][0];sum2+=a[x][1];dfs(x+1);sum1-=a[x][0];sum2-=a[x][1];sum1+=a[x][0];dfs(x+1);sum1-=a[x][0];sum2+=a[x][1];dfs(x+1);sum2-=a[x][1];}int main(){int t;cin>>t;while(t--){cnt=0;sum1=0;sum2=0;cin>>n>>h;for(int i=0;i<n;i++)cin>>a[i][0];for(int i=0;i<n;i++)cin>>a[i][1];dfs(0);printf("%d\n",cnt);}}