O - 酱神寻宝
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
酱神来到了一座小岛，岛上有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 and output
3 | 8 |
1 | 6 |
Hint
第一个样例中酱神会打开第一个和第二个箱子。
解题思路:
首先贪心，能用金 / 银就不用万能钥匙.
我们不妨令 f ( i , j ) -> 开启箱子的状态为 i , 金钥匙为 j 把时能获得最多的万能钥匙.
之后我们考虑更新,设 0 为没开启过， 1 为开启过.
每次更新都是由 x 个 0 的状态更新到 x+1 个 0 的状态.
我们采用bfs维护这种顺序即可
不过由于本题数据很水，各位可以尝试各种花式方法水过去!!
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
/*
f( i , j ) - > 当前开的箱子的集合为 i , 金钥匙的数目是 j 时可以获得的最多万能钥匙数目.
*/ using namespace std;
const int maxn = ;
int n,sta,stb,stc,f[ << ][ maxn* ],ans = ;
typedef struct Item
{
int needA,needB,getA,getB,getC;
}; typedef struct updatastatus
{
int st,number;
updatastatus(const int &st,const int &number)
{
this->st = st , this->number = number;
}
}; bool arrived[ << ][maxn * ];
queue<updatastatus>q;
Item A[maxn+]; inline void updata(int i,int j,int newans)
{
f[i][j] = max(f[i][j],newans);
} //可以开启为 0 ， 不能开启为 1； int main(int argc,char *argv[])
{
scanf("%d",&n);
for(int i = ; i < n ; ++ i) scanf("%d%d%d%d%d",&A[i].needA,&A[i].needB,&A[i].getA,&A[i].getB,&A[i].getC);
scanf("%d%d%d",&sta,&stb,&stc);
f[][sta] = stc; // Init;
memset(arrived,false,sizeof(arrived));
q.push(updatastatus(,sta));
while(!q.empty())
{
updatastatus ns = q.front();q.pop();
int ra = ns.number, rb, rc = f[ns.st][ns.number] , all = sta + stb + stc , st = ns.st;
for(int i = ; i < n ; ++ i)
if (ns.st >> i & )
all += A[i].getA + A[i].getB + A[i].getC - A[i].needA - A[i].needB;
ans = max(ans,all);
rb = all - ra - rc;
for(int i = ; i < n ; ++ i)
{
if (!(st >> i & ))
{
int needA = A[i].needA;
int needB = A[i].needB;
int getA = A[i].getA;
int getB = A[i].getB;
int getC = A[i].getC;
if (ra >= needA) //金够
{
if (rb >= needB) //金银都够
{
updata(st | ( << i) , ra - needA + getA, rc + getC);
if (!arrived[st | ( << i)][ra - needA + getA])
{
q.push(updatastatus(st | ( << i),ra - needA + getA));
arrived[st | ( << i)][ra - needA + getA] = true;
}
}
else //金够银不够
{
if (needB- rb <= rc)
{
updata(st | ( << i) , ra - needA + getA, rc - needB + rb + getC);
if (!arrived[st | ( << i)][ra - needA + getA])
{
q.push(updatastatus(st | ( << i),ra - needA + getA));
arrived[st | ( << i)][ra - needA + getA] = true;
}
}
}
}
else
{
if (rb >= needB) //金不够银够
{
if (needA - ra <= rc)
{
updata(st | ( << i) , getA, rc - needA + ra + getC);
if (!arrived[st | ( << i)][getA])
{
q.push(updatastatus(st | ( << i),getA));
arrived[st | ( << i)][getA] = true;
}
}
}
else //金不够银不够
{
if (needA - ra + needB - rb <= rc)
{
updata(st | ( << i) , getA, rc - needA + ra - needB + rb + getC);
if (!arrived[st | ( << i)][getA])
{
q.push(updatastatus(st | ( << i),getA));
arrived[st | ( << i)][getA] = true;
}
}
}
}
}
}
}
printf("%d\n",ans);
return ;
}