洛咕 P4131 [WC2005]友好的生物
2024-08-26 05:53:16
洛咕 P4131 [WC2005]友好的生物
首先可以发现\(C\)是没有用的,可以乘进所有的权值里面做
考虑没有最后一维的限制,那么两个生物的友好值就是
\(\sum_{i=1}^k|a_i-b_i|\)
这个绝对值就很麻烦了。
但是可以换个思路想,既然是绝对值那么一定\(\geq 0\),所以两个生物的友好值是
\(\max\left(\sum_{i=1}^k(a_i-b_i)(-1)^{c_i}\right)\)
其中\(c\)取遍所有的01数组。正确性是显然的,因为其他的都没有答案大。
那么这道题\(k\leq 5\),不考虑最后一维就是\(k=4\)。
上面的式子分开来考虑:
\(\max\left(\sum_{i=1}^ka_i(-1)^{c_i}+\sum_{i=1}^kb_i(-1)^{c_i+1}\right)\)
那么思路就很清晰了,对每个\(c\)记\(\max\left(\sum_{i=1}^kw_i(-1)^{c_i}\right)\)(记为\(Max_c\))以及取这个最大值的生物,
答案就是\(\max_{c_i+d_i=1}(Max_c+Max_d)\)
但是还有最后一维的限制,所以把生物按照最后一维排序,依次先和Max更新答案,再更新Max。在更新\(Max\)的时候减去最后一维更新,更新答案的时候加上最后一维
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct yyb{int a[4],b,i;}s[100010];
int S[100010][1<<4];
il bool operator<(const yyb&a,const yyb&b){return a.b<b.b;}
int Mx[1<<4],f[1<<4],C[6];
int main(){
int n=gi(),k=gi(),U=(1<<4)-1;
for(int i=0;i<k;++i)C[i]=gi();
for(int i=1;i<=n;++i){
for(int j=0;j<k-1;++j)s[i].a[j]=gi()*C[j];
for(int j=k-1;j<4;++j)s[i].a[j]=0;
s[i].b=gi()*C[k-1];
s[i].i=i;
}
k=4;
std::sort(s+1,s+n+1);
for(int i=1;i<=n;++i)
for(int j=0;j<1<<k;++j)
for(int l=0;l<k;++l)
if((1<<l)&j)S[i][j]+=s[i].a[l];
else S[i][j]-=s[i].a[l];
for(int i=0;i<1<<k;++i)Mx[i]=S[1][i]+s[1].b,f[i]=s[1].i;
int ans=-1e9,a=0,b=0;
#define chkans(t,_a,_b) {if((t)>ans)ans=(t),a=(_a),b=(_b);}
for(int i=2;i<=n;++i){
for(int j=0;j<1<<k;++j)chkans(Mx[U^j]+S[i][j]-s[i].b,s[i].i,f[U^j]);
for(int j=0;j<1<<k;++j)if(Mx[j]<S[i][j]+s[i].b)Mx[j]=S[i][j]+s[i].b,f[j]=s[i].i;
}
printf("%d %d\n%d\n",a,b,ans);
return 0;
}
最新文章
- Oracle 第一天
- 代码阅读工具:Source Navigator和Source Insight
- 多数浏览器默认会缓存input的值,只有使用ctl+F5强制刷新的才可以清除缓存记录。
- 修改后的CopyFile类
- .NET并行编程1 - 并行模式
- QlikView 权限设置问题和注意
- Winform开发框架中实现信息阅读状态的显示和存储
- 孙鑫MFC学习笔记2:C++回顾
- oracle的基本概念
- 解决insmod: error inserting &#39;hello.ko&#39;: -1 Invalid module format
- iOS NSData简单解析
- 如何查看linux系统下的各种日志文件 linux 系统日志的分析大全
- window.open打开新页面,并将本页数据用过url传递到打开的页面;需要两个页面;
- Qt Creator插件工作流程代码走读
- NYOJ115 市叛乱 【SPFA】
- 二维码(QR Code)生成与解析
- 【贪心】【堆】Gym -100956D - Greedy Game
- kafka集群中常见错误的解决方法:kafka.common.KafkaException: Should not set log end offset on partition
- 如何配置Open Live Writer程序以便更好的为博客服务
- 上传图片,通过node服务器存储在指定目录
热门文章
- mysql安装--常见
- Linux查看系统当前字符集
- C#(.NET)面试题:做一个能自定义输入命令的表格程序
- October 04th 2017 Week 40th Wednesday
- [EffectiveC++]item46:需要类型转换时请为模板定义非成员函数
- 面向对象程序设计_Task5_Calculator1.5.0
- 2、基于wsgiref模块DIY一个web框架
- js实现svg图形转存为图片下载[转]
- python3+OpenGL环境配置
- Python之美[从菜鸟到高手]--2+2=5