kartimisin's blog

One Japanese Problem

By kartimisin, 11 years ago, In English

"すぬけ君は N 匹の猫を飼っている。猫 i と猫 j の仲のよさは fi,j である。ある猫の幸福度は、その猫から距離 1 以内にいる猫との仲のよさの総和である。すぬけ君は、猫 1 から猫 N をこの順に一次元上に配置することにした。(猫 i の座標を xi とすると、xi は x1<x2<…<xN をみたす実数)　猫の幸福度の総和の最大値を求めよ。"

I can't translate this problem. Can anyone translate for me? Problems link: http://tdpc.contest.atcoder.jp/tasks/tdpc_cat

  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

You are raising N cats numbered by integers from 1 to N. When i-th cat and j-th cat's distance is less than or equal to 1, both of their happiness increases by fi, j. You want to allocate all of the cats at an one-dimension line, and maximize the sum of each cat's happiness. You should notice that i-th cat should be at (i + 1)-th cat's left side. (1 ≤ i < N)

Sorry for the bad English, if you couldn't understand it, please give me a comment :)

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Japanese is damned popular this week.

→ Reply