[东南大学第2届程序设计秋季赛 G] Hmmm: A Tricky Counting Challenge

Description

定义一个长度为 (n (n ge 2)) 的正整数数列 (a_1,a_2,...,a_n) 的权值为

[F(a_1,a_2,...,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) ]

给定一个长度为 (n) 的正整数数列 (a_1,a_2,...,a_n)。

定义一种交换操作：任意选择两个下标 (i,j) 满足 (1 le i < j le n)，交换 (a_i,a_j) 的值。

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

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

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

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

Solution

以下数列 ({a_i}) 指的均是原数列的任意一种排列。设

[b_1=a_1,b_n=a_n,b_i = max(min(max_{j=1}^{i-1} a_j, max_{j=i+1}^n a_j), a_i) (2 le i le n) ]

由 ({a_i}) 得到 ({b_i}) 的过程称为一次变换。对于任意一个数列 (a_i)，对 ((a_i,b_i)) 进行排序使 (b_i) 单调不升并且 (b_i) 相同时 (a_i) 单调不降，结果记做 ((a'_i,b'_i))，则 (b'_i) 仍是 (a'_i) 经过变换后的序列。利用动态规划统计所有可能的 ({b'_i}) 和有多少种取值即可。即用 (a_i) 中的元素去填 (b_i)，满足填出的 (b_i) 单调不降，并且第 (i) 大的元素至少要在第 (i) 个位置之后才可以出现。设 (f[t][i][j]) 表示考虑了 ({a_i}) 中前 (t) 大的元素，每个元素可以不使用或使用一次或多次，填了前 (b[1..i])，这 (i) 个数的和是 (j)，转移类似完全背包，用 std::bitset 优化即可。

改编自 [CCO 2017] 接雨滴

#include <bits/stdc++.h>
using namespace std;
#define int long long 
bitset <30005> f[505],ans;
int n,a[505],sum,res;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i], sum+=a[i];
    sort(a+1,a+n+1,greater<int>());
    f[1][a[1]]=1;
    for(int i=2;i<=n;i++,ans|=f[n]) for(int j=i;j<=n;j++) f[j]|=f[j-1]<<a[i];
    for(int i=sum;i<30005;i++) res+=ans[i];
    cout<<res;
}