seuOJ299 - Hmmm: A Tricky Counting Challenge

题目描述

定义一个长度为 n(n≥2)n (n \ge 2) 的正整数数列 a1,a2,…,ana_1,a_2,\ldots,a_n 的权值为

F(a1,a2,…,an)=∑i=2n−1max⁡(min⁡(max⁡j=1i−1(aj−ai),max⁡j=i+1n(aj−ai)),0)F(a_1,a_2,\ldots,a_n)=\sum_{i=2}^{n-1} \max(\min(\max_{j=1}^{i-1} (a_j-a_i), \max_{j=i+1}^n (a_j-a_i)), 0)

给定一个长度为 nn 的正整数数列 a1,a2,…,ana_1,a_2,\ldots,a_n。

定义一种交换操作：任意选择两个下标 i,ji,j 满足 1≤i<j≤n1 \le i < j \le n，交换 ai,aja_i,a_j 的值。

定义一个自然数 zz 是可达的，当且仅当可以通过任意多次（可以为 00 次）交换操作，使得 F(a1,a2,…,an)=zF(a_1,a_2,\ldots,a_n)=z 成立。换言之，zz 是可达的的充要条件是对原数列可以通过若干次交换操作来得到一个新数列，使得新数列的权值等于 zz。求可达的自然数共有多少个。

简而言之，即求对于给定数列通过任意次交换操作得到的所有数列中，数列权值的不同可能取值有多少种。

输入格式

第一行一个整数 n(1≤n≤500)n (1 \le n \le 500) 表示数列的长度。

第二行 nn 个正整数，第 ii 个正整数表示 ai(1≤ai≤50)a_i ( 1 \le a_i \le 50)。注意数列中可能会有相同的数。

输出格式

输出一个正整数，表示对于给定的数列，可达的自然数共有多少个。

样例

样例输入 1

3
1 2 3

样例输出 1

2

样例输入 2

5
2 1 2 1 2

样例输出 2

3

样例输入 3

5
1 1 4 5 5

样例输出 3

9

样例解释

第 11 组样例中，对于数列 1,2,31,2,3，由于数列本身权值为 00，故 00 是可达的；交换 1,21,2 后数列权值变为 11，故 11 也是可达的。可以证明，无论怎样交换，数列的权值不可能取得 0,10,1 外的数，因此对于数列 1,2,3,41,2,3,4 可达的自然数有且仅有 0,10,1 两个，故答案为 22。

第 22 组样例中，所有可达的自然数为 0,2,40,2,4。

第 33 组样例中，所有可达的自然数为 0,1,3,4,5,6,7,8,90,1,3,4,5,6,7,8,9。