AT_tdpc_cat.猫

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

すぬけ君养了 $N$ 只猫。猫 $i$ 和猫 $j$ 之间的亲密度为 $f_{i,j}$ 。某只猫的幸福度定义为与它距离不超过 1 的所有猫与它之间的亲密度之和。すぬけ君打算将猫 1 到猫 $N$ 按顺序排列在一维线上（设猫 $i$ 的坐标为 $x_i$ ，则 $x_i$ 满足 $x_1 < x_2 < \cdots < x_N$ ）。请你求出所有猫的幸福度之和的最大值。

输入格式

输入的第一行为一个整数 $N$ 。

接下来 $N$ 行，每行有 $N$ 个整数，第 $i$ 行第 $j$ 个整数为 $f_{i,j}$ 。

输出格式

输出一个整数，表示所有猫的幸福度之和的最大值。

说明/提示

数据范围

$1 \leq N \leq 1000$
$-1000 \leq f_{i,j} \leq 1000$
$f_{i,i} = 0$
$f_{i,j} = f_{j,i}$

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页