你发现 pizza 种类数不会很多,状压一下就可以了

code:

#include <bits/stdc++.h>
#define M 11
#define N 100005
#define LL long long
using namespace std;
int n,m,cnt;
int v[1<<M],tmp[M],id[1<<M],a1[1<<M],a2[1<<M];
LL val[1<<M];
LL mer[1<<M];
int tot[1<<M];
struct node
{
LL x;
int id;
node(LL x=0,int id=0):x(x),id(id){}
};
vector<node>gg[1<<M];
bool cmp(node a,node b)
{
return a.x<b.x;
}
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=0;i<=10;++i) tmp[i]=1<<i;
for(i=1;i<=n;++i)
{
int t,x,re=0;
scanf("%d",&t);
for(j=1;j<=t;++j) scanf("%d",&x),re|=tmp[x];
++v[re];
}
for(i=1;i<=m;++i)
{
LL x;
scanf("%lld",&x);
int t,o,re=0;
scanf("%d",&t);
for(j=1;j<=t;++j) scanf("%d",&o),re|=tmp[o];
if(!val[re]||val[re]>x) val[re]=x, id[re]=i;
gg[re].push_back(node(x,i));
}
for(i=1;i<tmp[10];++i) sort(gg[i].begin(),gg[i].end(),cmp);
for(i=1;i<tmp[10];++i)
{
if(!val[i]) continue;
if(gg[i].size()>=2)
{
if(!mer[i]||mer[i]>gg[i][0].x+gg[i][1].x)
mer[i]=gg[i][0].x+gg[i][1].x,a1[i]=gg[i][0].id, a2[i]=gg[i][1].id;
}
for(j=i+1;j<=tmp[10];++j)
{
if(!val[j]) continue;
if(!mer[i|j]||(mer[i|j]>val[i]+val[j]))
{
mer[i|j]=val[i]+val[j];
a1[i|j]=id[i];
a2[i|j]=id[j];
}
}
}
int mx=0;
for(i=1;i<=tmp[10];++i)
{
if(!mer[i]) continue;
tot[i]=0; // 枚举结合完的
for(j=1;j<=tmp[10];++j) { if((i&j)==j) tot[i]+=v[j]; }
if(!mx||(tot[i]>tot[mx])||(tot[i]==tot[mx]&&mer[i]<mer[mx])) mx=i;
}
// printf("%lld %d\n",mer[mx],tot[mx]);
printf("%d %d\n",a1[mx],a2[mx]);
return 0;
}

  

最新文章

  1. maven引入本地jar
  2. VHDL 学习
  3. C++ 面向对象编程
  4. Dual Palindromes
  5. share干什么的
  6. Hadoop2.4.1 64-Bit QJM HA and YARN HA + Zookeeper-3.4.6 + Hbase-0.98.8-hadoop2-bin HA Install
  7. Android getTopActivity的方法
  8. JAVA异常处理、常用类、反射、集合
  9. php中的foreach函数
  10. web.py 学习(二)Worker
  11. 完美结合 Redux 与 React-router (react-router不切换页面)
  12. Spring系列(1)--IOC 和 DI
  13. HDU 2015 偶数求和
  14. Spring Data Redis学习
  15. js数组之有已有数组创建新的数组
  16. Java关于网络编程回顾
  17. Vue如何引入远程JS文件
  18. 苹果手机连wifi跳不出来登录网页解决办法
  19. 【opencv】相机标定程序内存溢出
  20. SpringMVC-SimpleDEMO

热门文章

  1. canal+kafka订阅Mysql binlog将数据异构到elasticsearch(或其他存储方式)
  2. BBR 安装
  3. 状态机的Verilog写法
  4. java.lang.IllegalArgumentException: Expected authority at index 7: http:// 异常的原因
  5. MGR并行复制从节点复制线程死锁
  6. java接口幂等性校验
  7. 在centos7.6上部署.netcore 3.0 web程序
  8. [BZOJ2739]最远点(DP+分治+决策单调性)
  9. 树卷积神经网络Tree-CNN: A Deep Convolutional Neural Network for Lifelong Learning
  10. application.yml报错:a global security auto-configuration is now provided