状态压缩 hdu #10

You are playing CSGO.
There are n Main Weapons and m Secondary Weapons in CSGO. You can
only choose one Main Weapon and one Secondary Weapon. For each weapon,
it has a composite score S.

The higher the composite score of the weapon is, the better for you.

Also each weapon has K performance evaluations x[1], x[2], …, x[K].(range, firing rate, recoil, weight…)

So you shold consider the cooperation of your weapons, you want two
weapons that have big difference in each performance, for example, AWP +
CZ75 is a good choose, and so do AK47 + Desert Eagle.

All in all, you will evaluate your weapons by this formula.(MW for Main Weapon and SW for Secondary Weapon)

Now you have to choose your best Main Weapon & Secondary Weapon and output the maximum evaluation.

InputMultiple query.

On the first line, there is a positive integer T, which describe the number of data. Next there are T groups of data.

for each group, the first line have three positive integers n, m, K.

then, the next n line will describe n Main Weapons, K+1 integers each line S, x[1], x[2], …, x[K]

then, the next m line will describe m Secondary Weapons, K+1 integers each line S, x[1], x[2], …, x[K]

There is a blank line before each groups of data.

T<=100, n<=100000, m<=100000, K<=5, 0<=S<=1e9, |x[i]|<=1e9, sum of (n+m)<=300000

OutputYour output should include T lines, for each line, output the maximum evaluation for the corresponding datum.Sample Input

2

2 2 1

0 233

0 666

0 123

0 456

2 2 1

100 0 1000 100 1000 100

100 0

Sample Output

543

2000
题意 ： 有 n 种主武器， m 种副武器， 同时每种武器都有 k 个权值，询问上面所给的目标式子中的最大收益
思路分析 ： 考虑一下绝对值的性质， a-b 的绝对值等于 a-b 或者 -a+b , 并且题目所给的 k <= 5, 显然这里我们可以二进制去枚举，记录最大值即可
代码示例：

#define ll long long

const ll maxn = 1e5+5;

ll n, m, k;

ll a[maxn][10], b[maxn][10];

ll sa[50], sb[50];

void init() {

    ll f = 1;

    for(ll i = 1; i <= k; i++) f *= 2;

    memset(sa, 0x8f, sizeof(sa)); memset(sb, 0x8f, sizeof(sb));

    //printf("++ %lld \n", sa[0]);

    for(ll i = 1; i <= n; i++){

        for(ll state = 0; state < f; state++){

            ll sum = 0;

            for(ll j = 0; j < k; j++){

                if (state & (1<<j)) sum += a[i][j+1];

                else sum -= a[i][j+1];

            }

            sa[state] = max(sa[state], sum+a[i][0]);

        }

    }

    for(ll i = 1; i <= m; i++){

        for(ll state = 0; state < f; state++){

            ll sum = 0;

            for(ll j = 0; j < k; j++){

                if (state & (1<<j)) sum += b[i][j+1];

                else sum -= b[i][j+1];

            }

            sb[state] = max(sb[state], sum+b[i][0]);

        }

    }

}

void solve() {

    ll num = 1<<k;

    ll ans = 0x8f;

    for(ll i = 0; i < num; i++){

        ll pp = num-1-i;

        ans = max(ans, sa[i]+sb[pp]);

    }

    printf("%lld\n", ans);

}

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    ll t;

    cin >> t;

    while(t--){

        scanf("%lld%lld%lld", &n, &m, &k);

        for(ll i = 1; i <= n; i++){

            for(ll j = 0; j <= k; j++){

                scanf("%lld", &a[i][j]);

            }

        }

        for(ll i = 1; i <= m; i++){

            for(ll j = 0; j <= k; j++){

                scanf("%lld", &b[i][j]);

            }

        }

        init();

        solve();

    }

    return 0;

}

巴特西

状态压缩 hdu #10

最新文章

热门文章