bzoj5068: 友好的生物
2024-08-24 02:46:09
题目链接
题解
最大化这个东西\(\sum_{i=1}^{k-1} | a_{x,i}-a_{y,i} | - | a_{x,k}-a_{y,k} |\)
去掉绝对值号,也就是就是求这个式子 \(\sum_{i=1}^{k-1}±(a_{x,i}-a_{y,i}) - | a_{x,k} - a_{y,k} |\) 的最大值
对与前面的 \(i\) 式取 正负号 一定会有一个方案使每个 \(a_{x,i}-a_{y,i}\) 不负
装压枚举每个\(i\)的符号,对于 \(a_{x,k}\) 从小到大排序,维护前缀最小值更新答案
代码
#include<cmath>
#include<cstdio>
#include<algorithm>
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-')f = - 1; c = getchar(); }
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
#define INF 0x3f3f3f3f
int n,k;
struct A {
int d[10],id;
bool operator < (const A &a)const {
return d[k] < a.d[k];
}
} a[100007];
int c[76];
int main() {
n = read(),k = read() - 1;
for(int i = 0;i <= k;++ i) c[i] = read();
for(int i = 1;i <= n;++ i) {
a[i].id = i;
for(int j = 0;j <= k;++ j) a[i].d[j] = read(),a[i].d[j] *= c[j];
}
std::sort(a + 1,a + n + 1);
int ans = 0,id1,id2;
for(int s = 0;s < (1 << k); ++ s) {
int minn = INF, id;
for(int i = 1;i <= n;++ i) {
int ss = 0;
for(int j = 0;j < k;++ j)
if(s & (1 << j)) ss += a[i].d[j];
else ss -= a[i].d[j];
ss -= a[i].d[k ];
if(ans < ss - minn) ans = ss - minn,id1 = a[i].id,id2 = id;
if(minn > ss) minn = ss,id = a[i].id;
}
}
printf("%d\n",ans);
return 0;
}
最新文章
- Javascript初学篇章_4(循环与函数)
- MVC4 下DropDownList使用方法
- ACM题目————星际之门(一)
- spring定时任务的配置
- HDU 1175 连连看(BFS)
- Java调用天气Webservice的小应用
- 《JS权威指南学习总结--第八章 函数》
- java读写串口
- TM3、4波段GeoTiff数据计算NDVI
- LANMP On CentOS 6
- 高级软件工程第三次作业 赵坤&;黄亦薇
- ●BZOJ 2555 SubString
- 网页基础:网页设计(我所知道的所有的html和css代码(含H5和CSS3)),如有错误请批评指正
- JAVA锁有哪些种类,以及区别(转)
- java中int算法的有趣现象
- db2 事务日志
- 关于gitignore无效的一些记录
- 【DB2】建造测试数据
- POJ 3216 Repairing Company(最小路径覆盖)
- Linux主机添加路由和端口转发
热门文章
- vue.js react.js angular.js三者比较
- Spark记录-spark与storm比对与选型(转载)
- ngx_lua_API 指令详解(五)coroutine.create,coroutine.resume,coroutine.yield 等集合指令介绍
- Kafka 温故(一):Kafka背景及架构介绍
- 关于aspx.designer.cs
- Spring面试问答25题
- Python查找算法之 -- 列表查找和二分查找
- Java8系列之重新认识HashMap
- linux进程的一些日常处理
- Tomcat8 启动中提示 org.apache.catalina.webresources.Cache.getResource Unable to add the resource