[CCO 2017]接雨滴 [* interesting]
挺有意思的。
首先计算水滴量是不好的，可以考虑计算水滴量加上柱子高度的和。
首先不难注意到，我们在最大值的左侧和右侧同时添加权值是没有意义的，因为可以通过调整将他们调整至一边。（生成答案的部分单调排序即可）
所以可以规定最大值在第一个位置。
紧接着，我们发现答案可以近似视为选出次大值和一些元素，将他们从大到小排序，然后将其余元素插入在中间部分。
因为假设 (i) 比两端小，那么 (i) 是没有意义的，所以有效的元素一定是单调的，同时根据前文所述，强制让最大值位于 (1) 号位置后，后续的元素一定会构成一个单调栈。
这样可以从大到小将权值依次填入，不难发现我们此时对答案的描述即为 (sum c_i imes pre_i)。
于是设 (f_{k,i,j}) 表示考虑到第 (k) 个权值，当前考虑到位置 (i)，填入的权值和为 (j) 是否可行，转移只需要枚举 (t) 然后将 (f_{k-1,i-t,j-t imes c}) 转移过来即可。
不难发现转移本质上是一个完全背包，所以可以直接从前往后从 (f_{k,i-1,j-c}) 处转移。
通过 bitset 优化，容易得到一个 (mathcal O(frac{n^2sum h}{omega})) 的解法。
发现 (h) 非常小，同时不难发现每种 (h) 只需要转移一次，所以可以得到一个 (mathcal O(frac{nhsum h}{omega})) 的做法。（近似于 (mathcal O(frac{n^2h^2}{omega}))
唯一需要注意的就是为了确保大于 (j) 的元素一定可以被塞下去，对于第 (i) 大的权值我们需要从 (f_{k-1,i}) 处开始转移。
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 500 + 5 ;
const int M = 25000 + 5 ;
int n, S, h[N] ;
bitset<M> f[N], ans ;
signed main()
{
n = gi() ;
rep( i, 1, n ) h[i] = gi(), S += h[i] ;
sort(h + 1, h + n + 1, greater<int>()) ;
f[1][h[1]] = 1 ;
rep( i, 2, n ) {
if( (i != 2) && (h[i] == h[i - 1]) ) continue ;
rep( j, i, n ) f[j] |= (f[j - 1] << h[i]) ;
ans |= f[n] ;
}
for(re int i = S; i <= M - 5; ++ i)
if( ans[i] ) cout << i - S << " " ; puts("") ;
return 0 ;
}