酱神寻宝
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.uestc.edu.cn/#/problem/show/1141
Description
酱神来到了一座小岛，岛上有n个箱子。
一共有3中不同的钥匙，金钥匙、银钥匙和万能钥匙。酱神一开始有a把金钥匙、b把银钥匙和c把万能钥匙。
第i个箱子上有xi把金锁，yi把银锁。金钥匙只能打开金锁，银钥匙只能打开银锁，万能钥匙两种锁都能打开。用于打开锁的钥匙会立刻损坏，酱神会丢掉损坏的钥匙。箱子里有ai把金钥匙、bi把银钥匙和ci把万能钥匙，想要取出箱内的钥匙必须要打开这xi+yi把锁。
酱神的目的是使他拥有的钥匙总数最多。一旦酱神认为自己已经拥有了最多的钥匙，他就不会去开剩下的箱子了。
Input
第一行一个数n。
接下来有n行。每行5个数，xi,yi,ai,bi,ci。
最后一行3个数a,b,c。
1=<n<=15
0=<xi,yi,ai,bi,ci,a,b,c<=10
Output
输出一个数酱神的最多钥匙数。
Sample Input
3
1 0 0 0 1
2 4 0 8 0
3 9 10 9 8
3 1 2
Sample Output
8
HINT
题意
题解：
状压dp,借用一个贪心的思想，每次能用A就用A，不能再用万能钥匙
啊，用的bfs实现的
代码：
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
#define maxn 2000001
#define mod 10007
#define eps 1e-9
int Num;
char CH[];
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void P(int x)
{
Num=;if(!x){putchar('');puts("");return;}
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);
puts("");
}
//**************************************************************************************
struct Box
{
int a,b,c,d,e;
}box[]; struct node
{
int a,b;
}; int dp[<<][];
int main()
{
//test;
int n=read();
for(int i=;i<n;i++)
box[i].a=read(),box[i].b=read(),box[i].c=read(),box[i].d=read(),box[i].e=read();
int aa=read(),bb=read(),cc=read();
memset(dp,-,sizeof(dp));
dp[][aa]=cc;
queue<node>q;
q.push((node){,aa});
int ans=;
while(!q.empty())
{
node now=q.front();
q.pop();
int all=aa+bb+cc;
for(int i=;i<n;i++)
{
if(now.a>>i&)
{
all+=box[i].c+box[i].d+box[i].e-box[i].a-box[i].b;
}
}
ans=max(ans,all);
int nowa=now.b,nowc=dp[now.a][now.b],nowb=all-nowa-nowc;
//cout<<all<<" "<<nowa<<" "<<nowb<<" "<<nowc<<endl;
for(int i=;i<n;i++)
{
if(!(now.a>>i&))
{
if(nowa>=box[i].a)
{
if(nowb>=box[i].b)
{
if(nowc+box[i].e>dp[now.a|(<<i)][nowa-box[i].a+box[i].c])
{
dp[now.a|(<<i)][nowa-box[i].a+box[i].c]=nowc+box[i].e;
q.push((node){now.a|(<<i),nowa-box[i].a+box[i].c});
}
}
else if(nowc+nowb>=box[i].b)
{
if(nowc+box[i].e-box[i].b+nowb>dp[now.a|(<<i)][nowa-box[i].a+box[i].c])
{
dp[now.a|(<<i)][nowa-box[i].a+box[i].c]=nowc+box[i].e-box[i].b+nowb;
q.push((node){now.a|(<<i),nowa-box[i].a+box[i].c});
}
}
}
else if(nowa+nowc>=box[i].a)
{
int sp=nowc-box[i].a+nowa;
if(nowb>=box[i].b)
{
if(nowc+box[i].e-box[i].a+nowa>dp[now.a|(<<i)][box[i].c])
{
dp[now.a|(<<i)][box[i].c]=nowc+box[i].e-box[i].a+nowa;
q.push((node){now.a|(<<i),box[i].c});
}
}
else if(sp+nowb>=box[i].b)
{
if(sp+box[i].e-box[i].b+nowb>dp[now.a|(<<i)][box[i].c])
{
dp[now.a|(<<i)][box[i].c]=sp+box[i].e-box[i].b+nowb;
q.push((node){now.a|(<<i),box[i].c});
}
}
}
}
}
}
cout<<ans<<endl;
}