当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
2753：Similarity of necklaces
题目描述
The story is based on a real dream of mine. The description of rules is exactly what I dreamt. Do not start to code before you have understood it well.
The little cat is preparing a bead necklace for his girlfriend - a DIY one to express his affection. N (4 <= N <= 400) different kinds of beads (wooden, plastic, glass, pearl, DIAMOND!?, etc) have been kept in his huge casket, which are the only source of heads to make his necklace.
By the impulse of curiosity, the little cat made two strings of beads unthinkingly, one for him and one for his girlfriend – a pair of "lover-necklaces". Will his girlfriend like it? By the market research, how they look like depends on the similarity factor of two necklaces. A necklace can be considered as a linked list of M beads.
The similarity of two beads forms an N * N table. For example:
The similarity factor of two necklaces can be determined by the sum of M corresponding pair of beads. For example:
Necklace1: WPPWW
Necklace2: DPDDW
Similarly factor = Table[W,D] + Table[P,P] + Table[P,D] + Table[W,D] + Table[W,W] = -7 + 1 + 1 + (-7) + 6 = -6
Since we do not much care about what the necklace exactly is, (what is more, the little cat wants to keep it secret until his girlfriend's birthday) we use another N * N table to record number of existences of different pairs:
You are given the table Pairs, but to determine the table Table. The purpose is to make the similarity factor of two necklaces as large as possible. There's one more restriction holds for Table, Low[i, j] <= Table[i, j] <= Up[i, j] (an upper bound and an lower bound given to you). Obviously Low[i, j] = Low[j, i] and Up[i, j] = Up[j, i].
Background in my dream: the little cat has special magic. At one time, he can turn all the pearls to diamonds, and all the diamonds to pearls. More precise speaking, he can swap two different kinds of beads at one time. That is why N * N Pairs is fixed, but we can modify Table ourselves!
The little cat is preparing a bead necklace for his girlfriend - a DIY one to express his affection. N (4 <= N <= 400) different kinds of beads (wooden, plastic, glass, pearl, DIAMOND!?, etc) have been kept in his huge casket, which are the only source of heads to make his necklace.
By the impulse of curiosity, the little cat made two strings of beads unthinkingly, one for him and one for his girlfriend – a pair of "lover-necklaces". Will his girlfriend like it? By the market research, how they look like depends on the similarity factor of two necklaces. A necklace can be considered as a linked list of M beads.
The similarity of two beads forms an N * N table. For example:
The similarity factor of two necklaces can be determined by the sum of M corresponding pair of beads. For example:
Necklace1: WPPWW
Necklace2: DPDDW
Similarly factor = Table[W,D] + Table[P,P] + Table[P,D] + Table[W,D] + Table[W,W] = -7 + 1 + 1 + (-7) + 6 = -6
Since we do not much care about what the necklace exactly is, (what is more, the little cat wants to keep it secret until his girlfriend's birthday) we use another N * N table to record number of existences of different pairs:
You are given the table Pairs, but to determine the table Table. The purpose is to make the similarity factor of two necklaces as large as possible. There's one more restriction holds for Table, Low[i, j] <= Table[i, j] <= Up[i, j] (an upper bound and an lower bound given to you). Obviously Low[i, j] = Low[j, i] and Up[i, j] = Up[j, i].
Background in my dream: the little cat has special magic. At one time, he can turn all the pearls to diamonds, and all the diamonds to pearls. More precise speaking, he can swap two different kinds of beads at one time. That is why N * N Pairs is fixed, but we can modify Table ourselves!
输入解释
The input contains a number of test cases. Each of the following blocks denotes a single test case.
A test case starts by an integer N (4 <= N <= 400) and N lines followed. The i-th line followed contains 3 * (N – i + 1) integers, in which the j-th triple denotes Pairs[i, j + i - 1], Low[i, j + i - 1] and Up[i, j + i - 1].
Restrictions: -10000 <= Low[i, j] < Up[i, j] <= 10000, -100000 <= Pair[i, j] <= 100000. From the input given, you may assume that there is always a solution.
A test case starts by an integer N (4 <= N <= 400) and N lines followed. The i-th line followed contains 3 * (N – i + 1) integers, in which the j-th triple denotes Pairs[i, j + i - 1], Low[i, j + i - 1] and Up[i, j + i - 1].
Restrictions: -10000 <= Low[i, j] < Up[i, j] <= 10000, -100000 <= Pair[i, j] <= 100000. From the input given, you may assume that there is always a solution.
输出解释
For each test case, output a single line with a single number, which is the largest similarity that you can generate.
输入样例
4
7 1 10 0 -10 10 2 -10 10 0 -10 10
0 1 10 0 -10 10 0 -10 10
0 1 10 0 -10 10
0 1 10
4
0 1 10 2 -10 10 2 -10 10 2 -10 10
0 1 10 2 -10 10 2 -10 10
0 1 10 2 -10 10
0 1 10
输出样例
90 -4
提示
An optimum Table for the first sample case:
最后修改于 2020-10-29T06:41:44+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 2000 | 65536 |
登陆或注册以提交代码