比赛 |
Asm.Def战记之圣地亚哥“杯2015 |
评测结果 |
AAAAAWWAWW |
题目名称 |
Asm.Def的枪榴弹 |
最终得分 |
60 |
用户昵称 |
ziiidan |
运行时间 |
0.017 s |
代码语言 |
C++ |
内存使用 |
13.66 MiB |
提交时间 |
2019-10-23 17:42:03 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
const int maxn = 17;
int n, ans;
int nj, ny, nd;
int rob[maxn], fb[maxn], jia[maxn], yi[maxn], diao[maxn];
int a[maxn];
bool vis[maxn];
bool check(int kj, int ky, int ks, int rt)
{
int nd = 0;
if(kj < rob[rt]) nd += rob[rt] - kj;
if(ky < fb[rt]) nd += fb[rt] - ky;
if(nd > ks) return false;
return true;
}
void dfs(int pos, int kj, int ky, int ks)
{
ans = max(ans, kj + ky + ks);
if(pos == n + 1) return ;
for(int i = 1; i <= n; i++)
{
if(vis[i]) continue;
if(check(kj, ky, ks, i) == false) continue;
vis[i] = true;
int deltaj = 0, deltay = 0, deltas = 0;
if(kj < rob[i])
{
deltaj = kj;
deltas += (rob[i] - kj);
ks -= (rob[i] - kj);
kj = 0;
}
else {
deltaj = rob[i];
kj -= rob[i];;
}
if(ky < fb[i])
{
deltay = ky;
deltas += (fb[i] - ky);
ks -= (fb[i] - ky);
ky = 0;
}
else {
deltay = fb[i];
ky -= fb[i];
}
dfs(pos + 1, kj + jia[i], ky + yi[i], ks + diao[i]);
kj += deltaj;
ky += deltay;
ks += deltas;
vis[i] = false;
}
}
void Cal(void)
{
int sum = nj + ny + nd;
for(int i = 1; i <= n; i++)
{
if(a[i] == 0) continue;
sum += jia[i] + yi[i] + diao[i];
sum -= (rob[i] + fb[i]);
}
if(rand() % 3 == 0) ans = max(ans, sum);
}
void DFS(int pos)
{
if(pos == n + 1)
{
Cal();
return ;
}
a[pos] = 1;
DFS(pos + 1);
a[pos] = 0;
DFS(pos + 1);
}
int main()
{
freopen("asm_grenade.in", "r", stdin);
freopen("asm_grenade.out", "w", stdout);
srand(time(0));
cin >> n;
for(int i = 1; i <= n; i++) cin >> rob[i];
for(int i = 1; i <= n; i++) cin >> fb[i];
for(int i = 1; i <= n; i++) cin >> jia[i];
for(int i = 1; i <= n; i++) cin >> yi[i];
for(int i = 1; i <= n; i++) cin >> diao[i];
cin >> nj >> ny >> nd;
if(n <= 8)
{
dfs(1, nj, ny, nd);
cout << ans << '\n';
return 0;
}
DFS(1);
ans = max(ans, nj + ny + nd);
cout << ans << '\n';
return 0;
}