UESTC_酱神寻宝 2015 UESTC Training for Dynamic Programming

时间:2023-03-09 08:19:05
UESTC_酱神寻宝 2015 UESTC Training for Dynamic Programming<Problem O>

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

Sample Input Sample Output
3
1 0 0 0 1
2 4 0 8 0
3 9 10 9 8
3 1 2
8
1
0 0 1 2 3
0 0 0
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 ;
}