比赛 |
Asm.Def战记之圣地亚哥“杯2015 |
评测结果 |
AAAAAAAAAA |
题目名称 |
Asm.Def的枪榴弹 |
最终得分 |
100 |
用户昵称 |
fyb |
运行时间 |
0.008 s |
代码语言 |
C++ |
内存使用 |
0.48 MiB |
提交时间 |
2015-10-31 10:24:06 |
显示代码纯文本
#include <cstdio>
using namespace std;
#define NMAX 14
#define NUM 20000
struct st{int jia,yi,bing;};
int n,dfs_mx;
int a[NMAX],b[NMAX],c[NMAX],d[NMAX],e[NMAX];
st dp[NUM];
bool vis[NUM];
bool bu_hui_si(int ind,st num){
if(a[ind]<=num.jia)return (b[ind]<=num.yi+num.bing);
else return (b[ind]<=num.jia+num.yi+num.bing-a[ind]);
}
st sheng_duo_shao(int ind,st num){
st ans;
ans=num;
if(a[ind]<=ans.jia)ans.jia-=a[ind];
else{
ans.bing-=a[ind]-ans.jia;
ans.jia=0;
}
if(b[ind]<=ans.yi)ans.yi-=b[ind];
else{
ans.bing-=b[ind]-ans.yi;
ans.yi=0;
}
ans.jia+=c[ind];
ans.yi+=d[ind];
ans.bing+=e[ind];
return ans;
}
st dfs(int ind){
st tst,ans=(st){0,0,0};
int tmp,mx=0;
int i;
if(vis[ind])return dp[ind];
vis[ind]=true;
for(i=0;i<n;i++)
if(ind&(1<<i)){
// printf("%d\n",ind&~(1<<i));
tst=dfs(ind&~(1<<i));
if(bu_hui_si(i,tst)){
tst=sheng_duo_shao(i,tst);
if((tmp=tst.jia+tst.yi+tst.bing)>mx){
mx=tmp;
ans=tst;
if(tmp>dfs_mx)dfs_mx=tmp;
}
}
}
// printf("%x %d %d %d\n",ind,ans.jia,ans.yi,ans.bing);
return dp[ind]=ans;
}
int main(){
int k0,k1,k2;
int dp_end=0;
int i;
freopen("asm_grenade.in","r",stdin);
freopen("asm_grenade.out","w",stdout);
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",a+i);
for(i=0;i<n;i++)scanf("%d",b+i);
for(i=0;i<n;i++)scanf("%d",c+i);
for(i=0;i<n;i++)scanf("%d",d+i);
for(i=0;i<n;i++)scanf("%d",e+i);
scanf("%d%d%d",&k0,&k1,&k2);
dp[0]=(st){k0,k1,k2};
vis[0]=true;
for(i=0;i<n;i++)
dp_end|=1<<i;
dfs_mx=k0+k1+k2;
dfs(dp_end);
printf("%d\n",dfs_mx);
// printf("%d\n",sheng_duo_shao(1,(st){2,1,3}).yi);
return 0;
}