NC21776. 八意永琳的药房
描述
输入描述
输入第一行包括一个整数n
接下来n行,每行一个数字ai,表示该种主材料的产地数量 紧接着是ai个整数kj,表示不同产地的材料品级
1<=n<=100 , 1<=ai<=10000,1<=ki<=300
输出描述
输出一个整数,表示可能的种类数量
示例1
输入:
5 1 1 1 1 2 1 2 3 1 2 3 1 100
输出:
4
C++14(g++5.4) 解法, 执行用时: 1268ms, 内存消耗: 616K, 提交时间: 2018-12-23 13:26:09
#include <bits/stdc++.h>
using namespace std;
int main()
{
bitset<30000+100> now,ans;
int n;
scanf("%d",&n);
ans[0]=1;
while(n--)
{
int t,v; scanf("%d",&t);
now=ans;
for(int i=1;i<=t;i++)
{
scanf("%d",&v);
if(i==1)
{
ans=(ans<<v);
continue;
}
ans|=now<<v;
}
//cout<<"debug"<<ans<<endl;
}
cout<<ans.count()<<endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1584ms, 内存消耗: 504K, 提交时间: 2018-12-22 14:46:30
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
bitset<30010> b[2];
int n;
int main()
{
scanf("%d",&n);
b[0].set(0);
for(int i=1,c,x;i<=n;i++)
{
scanf("%d",&c);
b[i&1]=0;
for(int j=1;j<=c;j++)
{
scanf("%d",&x);
b[i&1]|=b[(i&1)^1]<<x;
}
}
printf("%d\n",b[n&1].count());
}