比赛 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;
}