hdu3182 状态压缩水题
题意是这种 给你n个汉堡 每一个汉堡有它的价值 做每一个汉堡都得花费相应的能量 如今告诉你最大能量 让你求获得的最大的价值(有些汉堡必须有还有一些汉堡做好为前提)
给你的n你最大为15
这道题的重点在于 每一个汉堡仅仅能做一次 跑遍所以的状态 mark记录每一个状态下所剩余的能量 dp数组记录每一个状态下的获得的最大的价值
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int value[20],cost[20],need[20][20],n,m;
int mark[1<<16],dp[1<<16];
int Max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int T,i,j,a,b;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&value[i]);
}
for(i=1;i<=n;i++)
scanf("%d",&cost[i]);
memset(need,0,sizeof(need));
for(i=1;i<=n;i++)
{
scanf("%d",&need[i][0]);
for(j=1;j<=need[i][0];j++)
{
scanf("%d",&need[i][j]);
}
}
memset(mark,0,sizeof(mark));
for(i=0;i<(1<<n);i++)
dp[i]=-10000000;
dp[0]=0;
mark[0]=m;
int flash,k=0,x;
for(i=0;i<=(1<<n)-1;i++)
{
for(j=1;j<=n;j++)
{
x=(1<<(j-1));
if(i&x) continue;
int now=i|(1<<(j-1));
flash=0;
for(int t=1;t<=need[j][0];t++)
{
if(!(i&(1<<((need[j][t])-1)))) {flash=1;break;}
}
if(!flash&&dp[now]<dp[i]+value[j]&&mark[i]>=cost[j])
{
mark[now]=mark[i]-cost[j];
dp[now]=dp[i]+value[j];
k=Max(dp[now],k);
}
}
}
printf("%d\n",k);
}
return 0;
}
最新文章
- HTML label标签的一点理解
- 【GO】GO语言学习笔记二
- Android 各层调用的方式
- Jquery 的事件方法
- 接口测试从未如此简单 - Postman (Chrome插件)【转】
- 【JavsScript】推荐五款流行的JavaScript模板引擎
- Intent的4种传值方法总结
- SharePoint REST api
- Js点餐加减数量
- Lintcode--005(最长公共子序列)
- UML学习笔记之类之间的关系
- css中,如何设置前景色的透明度?
- java线程优先级
- mybatis 直接执行sql 【我】
- 修改Visual Studio项目中程序集信息默认公司名称的两种方法
- Linux中Postfix邮件安装Maildrop(八)
- 2019.4.25 表格表单与HTML5 &;&; CSS3
- Mac 导入maven项目详解
- python+echarts==pycharts
- Redis未授权访问反弹shell
热门文章
- exit()和_exit()和return
- 【ASP.NET】验证控件
- BASH Shell 简易进度条小函数
- 如何解决This system is not registered with RHN.
- 【足迹C++primer】30、概要(泛型算法)
- 三点半们耐热i哦好家哦i囧囧【
- uva 11722 - Joining with Friend(概率)
- spring的长处 ioc aop
- 堆栈帧的组织——C/C++内存管理必须掌握
- asp.net Form 认证【转】