猫
题意翻译
有人饲养了n只猫。
猫[i]和猫[j]的友好指数为f[i,j],
猫的幸福指数是指与距离1以内的猫的友好指数的总和。
此人按照从猫[1]到猫[n]的顺序把猫配置于一维上。
(猫[i]的坐标为x[i],x[i]是满足x[1]小于x[2]……小于x[n]的实数)
求猫的幸福指数总和的最大值。
题目描述
[problemUrl]: https://atcoder.jp/contests/tdpc/tasks/tdpc_cat
入力は以下の形式で標準入力から与えられる。
> $ N $ $ f_{1,1}\ ...\ f_{1,N} $ $ ... $ $ f_{N,1}\ ...\ f_{N,N} $
答えを一行に出力せよ。 ```
3
0 2 3
2 0 -10
3 -10 0
```
```
4
```
```
5
0 -3 5 2 -6
-3 0 6 -3 1
5 6 0 2 0
2 -3 2 0 4
-6 1 0 4 0
```
```
28
```
输入输出格式
输入格式
输出格式
输入输出样例
暂无测试点说明
### Constraints
すぬけ君は $ N $ 匹の猫を飼っている。猫 $ i $ と猫 $ j $ の仲のよさは $ f_{i,j} $ である。ある猫の幸福度は、その猫から距離 1 以内にいる猫との仲のよさの総和である。すぬけ君は、猫 1 から猫 $ N $ をこの順に一次元上に配置することにした。(猫 i の座標を $ x_i $ とすると、$ x_i $ は $ x_1\ をみたす実数) 猫の幸福度の総和の最大値を求めよ。
1\ <\ =\ N\ <\ =\ 1000 $
3. $ -1000\ <\ =\ f_{i,j}\ <\ =\ 1000 $
4. $ f_{i,i}\ =\ 0 $
5. $ f_{i,j}\ =\ f_{j,i} $