选择困难症
小L有严重的选择困难症。
早上起床后，需要花很长时间决定今天穿什么出门。
假设一共有k类物品需要搭配选择，每类物品的个数为Ai，每个物品有一个喜欢值Vj，代表小L对这件物品的喜欢程度。
小L想知道，有多少种方案，使得选出来的总喜欢值>M
需要注意，每类物品，至多选择1件，可以不选。
输入描述:
多组输入
每组数据第一行输入k M(k<=6,1<=M<=1e8)，表示有多少类物品
接下来k行，每行以Ai(1<=Ai<=100)开头，表示这类物品有多少个，接下来Ai个数，第j个为Vj(1<=Vj<=1e8),表示小L对这类物品的第j个的喜欢值是多少。
输出描述:
每组输出一行，表示方案数
输入
2 5
3 1 3 4
2 2 3
2 1
2 2 2
2 2 2
输出
3
8
题解：纯dfs会t，所以需要优化。就需要一些优化，可以用用一个mul数组来描述到次层方案时的后续方案数，如果本层此次已经大于sum，就直接加上后续所用的方案数，return就ok了。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
int k,m,a[8][105],num[8];
ll mul[8],res;
void dfs(int cur,int sum)
{
if(cur>k)
return ;
for(int i=0;i<=num[cur];i++)
{
if(sum+a[cur][i]>m)
{
res+=mul[cur+1]*(num[cur]-i+1);
return ;
}
dfs(cur+1,sum+a[cur][i]);
}
}
int main()
{
while(scanf("%d%d",&k,&m)!=EOF)
{
for(int i=1;i<=k;i++)
{
scanf("%d",&num[i]);
for(int j=1;j<=num[i];j++)
scanf("%d",&a[i][j]);
sort(a[i]+1,a[i]+1+num[i]);
}
mul[k+1]=1;
for(int i=k;i>=1;i--)
mul[i]=mul[i+1]*(num[i]+1);
res=0;
dfs(1,0);
printf("%lld\n",res);
}
return 0;
}
相关阅读
在参加面试的最后，面试官通常会说“有什么要问我的嘛？”在没想到更好的问题时，我们通常会选择咨询一个跟前途相关的问题“我这份岗位
1.1 服务器平台选择Windows, LINUX, BSD均可，推荐使用LINUX。本文以Centos7.0 64位服务器为例说明。如果希望服务器能被全国其他人
直接选择排序：思路（按升序）：第一轮要在位置0找到最小的元素，所以0要与（0+1）~length-1挨个比；第二轮要在位置1找到第二小的元素，所以1要与（1+
有些人找兼职觉得很困难，有些人却认为很简单。那是因为有些人找到了一个捷径，那就是兼职库。兼职库里有各行各业所需要的兼职工作
感同身受的去理解用户，才能获得他们的认可，才能做出令人着迷的产品。其实不管是什么商业模式、什么产品，其产生价值的前提就是理解你