ZZY的困惑
2024-10-09 20:38:22
Description
ZZY有很多爱好~~比如足球、电影、三国杀、A题,而他希望在这些爱好中能收获一些东西~~但是并不是所有爱好对所有目标都是起积极作用的..ZZY十分的困惑..于是列了下自己想获得的收获并且给每个目标设立了最小要达到的权值...并且给自己的爱好对每个收获目标进行了评值..这个值若是负则代表不利于获得某个收获~~为0代表没影响~~为正的代表利于获得某种收获..现在ZZY已经制作好了这些数据想请你帮帮忙~~在保证所有的目标最低要求都能达成的情况下保留尽量多的爱好~~
Input
多组数据读到EOF结束(不超过10组)每组数据
第一行为ZZY的收获目标个数N ( 0<N<=20 )
第二行为ZZY对每个目标所订的一个最低权值 ( 0 < w <= 1000 )
第三行为ZYY的爱好总数M ( 0 < M <= 16 )
下面的M行每行有N个数代表每个爱好对每个目标的促进权值..( -1000 <= k <= 1000 )
Output
每组输入对应一行输出:
第一个数为能保留的最多爱好个数..紧接着为这些爱好分别对应输入的是那几个序号..
若有多种都能达到保留个数请输出相对来说较小的(如 1 2 与 3 4 同时能满足要求,那么选1 2)
若怎么都无法实现目标那只能说着所有爱好都要不得,输出0...
Sample Input
4 100 200 300 400 3 100 100 400 500 100 -10 50 300 100 100 -50 -50
Sample Output
2 1 3
#include <stdio.h>
#include <string.h>
#define maxn 22 int n,m;
int need[maxn];
int sum[maxn][<<];
int help[maxn][<<]; bool check(int sta)
{
for(int i=; i<n; i++)
{
if(sum[i][sta]<need[i])
return false;
}
return true;
}
int lowbit(int x)
{
return x&-x;
}
int cnt[<<]; int main()
{
int i,j,k;
cnt[]=;
int all=(<<);
for(i=; i<all; i++) cnt[i]=cnt[i-lowbit(i)]+;
while(~scanf("%d",&n))
{
for(i=; i<n; i++) scanf("%d",&need[i]);
scanf("%d",&m);
for(i=; i<m; i++)
for(j=; j<n; j++) scanf("%d",&help[j][<<i]);
memset(sum,,sizeof(sum));
int maxret=,ret=;
for(i=; i<(<<m); i++)
{
int x=lowbit(i);
for(j=; j<n; j++) sum[j][i]=sum[j][i-x]+help[j][x];
if(check(i))
if(cnt[i]>maxret)
{
maxret=cnt[i]; //cnt[i]记录爱好的个数
ret=i; //ret利用二进制压缩法记录爱好的次序
}
}
printf("%d",maxret);
for(i=; i<m; i++)
{
if(ret&(<<i))
printf(" %d",i+);
}
puts("");
}
return ;
}
最新文章
- 常用 meta 整理
- dubbo入门示例
- 自适应UITableView的Cell高度问题
- Asp.Net工作原理
- 简易的IOS位置定位服务
- 《深入浅出WPF》笔记四
- com.intellij.javaee.oss.admin.jmx.JmxAdminException: com.intellij.execution.ExecutionException idea 导出war 报错
- flume 自己定义 hbase sink 类
- Java--日期的使用
- Selinux是什么?
- (python功能定制)复杂的xml文件对比,产生HTML展示区别
- machine learning 之 logistic regression
- U盘分区后合并
- Vue-起步篇:Vue与React、 Angular的区别
- mybatis中的动态SQL
- html布局(盒子)
- 小小知识点(一)——利用电脑自带的BitLocker对磁盘加密
- 763. Partition Labels 相同字母出现在同一块中,且块数最多
- 连接db2数据库出现No buffer space available (maximum connections reached?)
- 自动色彩均衡(ACE)快速算法