BZOJ5068: 友好的生物(状压 贪心)
程序员文章站
2022-05-18 22:54:59
题意 "题目链接" Sol 又是一道神仙题??。。 把绝对值拆开之后状压前面的符号?。。 下界显然,但是上界为啥是对的呀qwq。。 cpp include using namespace std; const int MAXN = 1e6 + 10; inline int read() { char ......
题意
sol
又是一道神仙题??。。
把绝对值拆开之后状压前面的符号?。。
下界显然,但是上界为啥是对的呀qwq。。
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, k, c[maxn], ans; struct node { int v[6], vk; bool operator < (const node &rhs) const { return vk < rhs.vk; } }a[maxn]; int main() { n = read(); k = read() - 1; for(int i = 0; i <= k; i++) c[i] = read(); for(int i = 1; i <= n; i++) { for(int j = 0; j < k; j++) a[i].v[j] = read() * c[j]; a[i].vk = read() * c[k]; } sort(a + 1, a + n + 1); for(int sta = 0; sta < (1 << k); sta++) { int mn = 1e9 + 10; for(int i = 1; i <= n; i++) { int now = 0; for(int j = 0; j < k; j++) now += (sta >> j & 1) ? -a[i].v[j] : a[i].v[j]; now -= a[i].vk; ans = max(ans, now - mn); mn = min(now, mn); } } cout << ans; return 0; } /* 5 3 1 2 3 -5 3 2 -2 3 0 0 5 9 3 4 -1 -10 -11 7 */
上一篇: 设计模式的简单理解——单例模式
下一篇: NOIP游记 Day0