[ONTAK2010]Peaks 题解
题目地址:BZOJ:Problem 3545. — [ONTAK2010]Pe …
May all the beauty be blessed.
题目地址:BZOJ:Problem 2430. — [Poi2003]Chocolate
有一块n*m的矩形巧克力,准备将它切成n*m块。巧克力上共有n-1条横线和m-1条竖线,你每次可以沿着其中的一条横线或竖线将巧克力切开,无论切割的长短,沿着每条横线切一次的代价依次为y1,y2,…,yn-1,而沿竖线切割的代价依次为x1,x2,…,xm-1。例如,对于下图6*4的巧克力,
我们先沿着三条横线切割,需要3刀,得到4条巧克力,然后再将这4条巧克力沿竖线切割,每条都需要5刀,则最终所花费的代价为y1+y2+y3+4*(x1+x2+x3+x4+x5)。
当然,上述简单切法不见得是最优切法,那么怎样切割该块巧克力,花费的代价最少呢?
要把一个大矩形横着切n-1刀竖着切m-1刀分成n*m个小矩形,从左到右从上到下每个位置切一刀都有一个代价,每一次对一整块(不论大小,无法一刀切断多块)切一次都会产生一次代价,求切割的最小代价。
输入格式:
第一行为两个整数n和m。
接下来n-1行,每行一个整数,分别代表x1,x2,…,xn-1。
接下来m-1行,每行一个整数,分别代表y1,y2,…,ym-1。
输出格式:
输出一整数,为切割巧克力的最小代价。
输入样例#1:
6 4 2 1 3 1 4 4 1 2
输出样例#1:
42
30%的数据,n<=100,m<=100
100%的数据,n<=10000,m<=10000
贪心。
一定是先切掉代价较大的位置。考虑证明它,对于平行的刀切位置,在一个序列中先切代价大的,由于每一刀要乘上与位置垂直的位置已经切了几刀这个数字,因此越靠前乘的数字越小,总和越小。对于垂直的两个刀切位置,先切代价较大的那个,若先切较小的,较大的乘的数字会+1,比先切较大的更劣。
由于需要排序,复杂度O(n \log n)。
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <functional>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
return res * neg;
}
const int MAXN = 20005;
struct Node {
int w;
bool type;
inline bool operator>(const Node &rhs) const {
return w > rhs.w;
}
};
int n, m;
std::vector<Node> vec;
int main() {
n = readint(); m = readint();
for(int i = 1, t; i < n; i++) {
t = readint(); vec.push_back(Node {t, 0});
}
for(int i = 1, t; i < m; i++) {
t = readint(); vec.push_back(Node {t, 1});
}
std::sort(vec.begin(), vec.end(), std::greater<Node>());
int ch = 1, cv = 1, ans = 0;
for(int i = 0; i < vec.size(); i++) {
ans += vec[i].w * (vec[i].type ? ch : cv);
if(vec[i].type) cv++; else ch++;
}
printf("%d", ans);
return 0;
}
题目地址:洛谷:【P3584】[POI2015]LAS – 洛谷、BZOJ:Problem 3749. — [POI2015]Łasuchy
圆桌上摆放着n份食物,围成一圈,第i份食物所含热量为c[i]。 相邻两份食物之间坐着一个人,共有n个人。每个人有两种选择,吃自己左边或者右边的食物。如果两个人选择了同一份食物,这两个人会平分这份食物,每人获得一半的热量。 假如某个人改变自己的选择后(其他n-1个人的选择不变),可以使自己获得比原先更多的热量,那么这个人会不满意。 请你给每个人指定应该吃哪一份食物,使得所有人都能够满意。
输入格式:
第一行一个整数n(2<=n<=1000000),表示食物的数量(即人数)。食物和人都从1~n编号。
第二行包含n个整数c[1],c[2],…,c[n] (1<=c[i]<=10^9)。
假设第i个人(1<=i<n)左边是第i份食物,右边是第i+1份食物;而第n个人左边是第n份食物,右边是第1份食物。
输出格式:
如果不存在这样的方案,仅输出一行NIE。
如果存在这样的方案,输出一行共n个整数,第i个整数表示第i个人选择的食物的编号。如果有多组这样的方案,输出任意一个即可。
输入样例#1:
5 5 3 7 2 9
输出样例#1:
2 3 3 5 1
是一个动态规划的判定问题。我们可以枚举第一个食物被左边/右边/两边/没被吃的情况,然后通过递推获得后面的食物的某个状态的可行性。
例如,当前一个食物被左边的人吃了,显然当前食物是必须让当前的左边的人吃掉的,而枚举剩下的情况,就是右边的人吃不吃,从而判断左边的人吃当前食物对他来说是否是最优的。
我们可以在DP的过程中记下上一个状态,在输出方案的时候倒推统计每个人吃的是什么食物,这样就可以输出方案了。
这个DP的复杂度是O(n)的。
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
return res * neg;
}
const int MAXN = 1000005;
// 1: left 2: right 3: both 4: neither
int n, dp[MAXN][5];
LL c[MAXN];
inline bool caldp(int s) {
memset(dp, 0, sizeof(dp));
dp[1][s] = 1;
for(int i = 2; i <= n + 1; i++) {
if(dp[i - 1][1] && c[i - 1] <= c[i] * 2) dp[i][1] = 1;
if(dp[i - 1][1] && c[i - 1] <= c[i]) dp[i][3] = 1;
if(dp[i - 1][2] && c[i - 1] * 2 >= c[i]) dp[i][2] = 2;
if(dp[i - 1][2] && c[i - 1] >= c[i]) dp[i][4] = 2;
if(dp[i - 1][3] && c[i - 1] >= c[i]) dp[i][2] = 3;
if(dp[i - 1][3] && c[i - 1] >= c[i] * 2) dp[i][4] = 3;
if(dp[i - 1][4] && c[i - 1] <= c[i]) dp[i][1] = 4;
if(dp[i - 1][4] && c[i - 1] * 2 <= c[i]) dp[i][3] = 4;
}
return dp[n + 1][s];
}
int ans[MAXN];
int main() {
n = readint();
for(int i = 1; i <= n; i++) {
c[i] = readint();
}
c[n + 1] = c[1];
bool success = false;
for(int i = 1; i <= 4; i++) {
if(caldp(i)) {
int type = i;
for(int i = n + 1; i >= 1; i--) {
if(type == 1) ans[i - 1] = (i - 1) % n + 1;
if(type == 2) ans[i] = (i - 1) % n + 1;
if(type == 3) ans[i - 1] = ans[i] = (i - 1) % n + 1;
type = dp[i][type];
}
for(int i = 1; i <= n; i++) {
printf("%d ", ans[i]);
}
return 0;
}
}
puts("NIE");
return 0;
}
题目地址:洛谷:【P3159】[CQOI2012]交换棋子 – 洛谷、BZOJ:Problem 2668. — [cqoi2012]交换棋子
有一个n行m列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。
输入格式:
第一行包含两个整数n,m(1<=n, m<=20)。以下n行为初始状态,每行为一个包含m个字符的01串,其中0表示黑色棋子,1表示白色棋子。以下n行为目标状态,格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串,表示每个格子参与交换的次数上限。
输出格式:
输出仅一行,为最小交换总次数。如果无解,输出-1。
输入样例#1:
3 3 110 000 001 000 110 100 222 222 222
输出样例#1:
4
如果我们把棋盘上看做只有黑色棋子,那么可以把交换达到目标状态看做把每个黑色棋子移动到目标位置上去。在移动的过程中,起终点格子各参与一次交换,路径上的其他格子各参与两次交换。既然如此,我们可以把次数上限平分成向上一步交换和向下一步交换两部分。
建图的时候,把每个格子拆成三个点,入点、原点、出点,流的方向应该是入点→原点→出点,这三个点之间的边,容量均为次数上限的一半,不妨把交换次数(费用)放在入点→原点的边上,可以避免算多交换次数。
对于初始状态的黑点格子,从源向该格子的原点连容量1费用0的边,对于目标状态的黑点格子,从该格子的原点向汇连容量1费用0的边,对于有公共点/边的格子,从出点向入点连容量无限费用0的边。至此网络就建立完成了,只需要跑最小费用最大流,若满流则答案为费用,否则无解。
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <queue>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
return res * neg;
}
inline int readdigit() {
char c;
while(!isdigit(c = fgc())) {}
return c - '0';
}
const int MAXN = 100005, INF = 1e9;
struct Edge {
int to, cap, cost, nxt;
} gra[MAXN << 4];
int head[MAXN], tot;
inline void addedge(int u, int v, int cap, int cost) {
gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}
int dis[MAXN], f[MAXN], pre[MAXN], pree[MAXN];
std::queue<int> que;
bool inque[MAXN];
inline bool spfa(int s, int t) {
memset(dis, 0x3f, sizeof(dis));
memset(f, 0, sizeof(f));
dis[s] = 0; f[s] = INF; inque[s] = true; que.push(s);
while(!que.empty()) {
int u = que.front(); que.pop(); inque[u] = false;
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(gra[i].cap && dis[v] > dis[u] + gra[i].cost) {
dis[v] = dis[u] + gra[i].cost;
f[v] = std::min(f[u], gra[i].cap);
pre[v] = u; pree[v] = i;
if(!inque[v]) {
que.push(v); inque[v] = true;
}
}
}
}
return f[t];
}
int flow, cost;
inline void mcmf(int s, int t) {
while(spfa(s, t)) {
flow += f[t]; cost += f[t] * dis[t];
for(int i = t; i != s; i = pre[i]) {
gra[pree[i]].cap -= f[t]; gra[pree[i] ^ 1].cap += f[t];
}
}
}
const int fix[][8] = {{-1, 1, -1, 1, -1, 1, 0, 0}, {0, 0, -1, 1, 1, -1, -1, 1}};
int n, m, cnt, st[25][25], ed[25][25], lim[25][25], S, T;
int main() {
memset(head, -1, sizeof(head));
n = readint(); m = readint(); S = n * m * 3 + 1; T = S + 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
st[i][j] = readdigit();
if(st[i][j]) cnt++;
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
ed[i][j] = readdigit();
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
lim[i][j] = readdigit();
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(st[i][j]) addedge(S, (i - 1) * m + j, 1, 0);
if(ed[i][j]) addedge((i - 1) * m + j, T, 1, 0);
if(st[i][j] && !ed[i][j]) {
addedge(n * m + (i - 1) * m + j, (i - 1) * m + j, lim[i][j] / 2, 1);
addedge((i - 1) * m + j, n * m * 2 + (i - 1) * m + j, (lim[i][j] + 1) / 2, 0);
} else if(!st[i][j] && ed[i][j]) {
addedge(n * m + (i - 1) * m + j, (i - 1) * m + j, (lim[i][j] + 1) / 2, 1);
addedge((i - 1) * m + j, n * m * 2 + (i - 1) * m + j, lim[i][j] / 2, 0);
} else {
addedge(n * m + (i - 1) * m + j, (i - 1) * m + j, lim[i][j] / 2, 1);
addedge((i - 1) * m + j, n * m * 2 + (i - 1) * m + j, lim[i][j] / 2, 0);
}
for(int k = 0; k < 8; k++) {
int nx = i + fix[0][k], ny = j + fix[1][k];
if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
addedge(n * m * 2 + (i - 1) * m + j, n * m + (nx - 1) * m + ny, INF, 0);
}
}
}
mcmf(S, T);
printf("%d", flow >= cnt ? cost : -1);
return 0;
}