状态压缩 hdu #10

时间：2018-10-01 11:25:43 阅读：156 评论：0 收藏：0 [点我收藏+]

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

原文：https://www.cnblogs.com/ccut-ry/p/9734351.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)