menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[去绝对值]HDU6435(2018多校训练赛第十场)【CSGO】题解
apps HDU
local_offer 查看标签
comment 0 条评论

题目概述

你在play♂CSGO,被第 $i$ 种枪打跪体现你有 $S_i$ 的手残值,并且有 $K$ 个参数 $\{x_{i,K}\}$ ,被第 $j$ 种刀捅挂体现你有 $S_j$ 的手残值,并且也有 $K$ 个参数 $\{y_{j,K}\}$ 。你每次都会被一种枪打跪之后用刀捅挂,这时候体现了你有 $S_i+S_j+\sum_{k=1}^{K}|x_{i,k}-y_{j,k}|$ 的手残值。请问你体现出的手残值最大为多少。

解题报告

一个套路,把绝对值看成 $max\{x-y,y-x\}$ ,由于要求值最大所以不合法的那种(负数)一定不会选,就可以达到去除绝对值的效果。

那么只需要 $2^K$ 枚举每个参数的正负情况,然后求 $max\{S_i+f_kx_{i,k}\}+max\{S_j-f_ky_{j,k}\}$ 的最大值就是答案。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int te,n,m,K,A[maxn+5],B[maxn+5],x[maxn+5][5],y[maxn+5][5];LL ans;

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d%d",&n,&m,&K);ans=0;
        for (int i=1;i<=n;i++) {scanf("%d",&A[i]);for (int j=0;j<K;j++) scanf("%d",&x[i][j]);}
        for (int i=1;i<=m;i++) {scanf("%d",&B[i]);for (int j=0;j<K;j++) scanf("%d",&y[i][j]);}
        for (int s=0;s<(1<<K);s++){
            LL MAXA=-(9e18),MAXB=-(9e18);
            for (int i=1;i<=n;i++){
                LL sum=A[i];for (int j=0;j<K;j++) if (s>>j&1) sum+=x[i][j]; else sum-=x[i][j];
                MAXA=max(MAXA,sum);
            }
            for (int i=1;i<=m;i++){
                LL sum=B[i];for (int j=0;j<K;j++) if (s>>j&1) sum-=y[i][j]; else sum+=y[i][j];
                MAXB=max(MAXB,sum);
            }
            ans=max(ans,MAXA+MAXB);
        }printf("%lld\n",ans);
    }
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up