脚本宝典收集整理的这篇文章主要介绍了题解 P6345 [CCO 2017]接雨滴，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

解题思路

NOIP在即，感觉即将退役，或许是最后一篇题解了。。。

求水的体积不是特别好求，我们考虑求出 水+柱子 的体积最后再减去柱子的体积。

发现对于最高的柱子在中间的情况其实可以把最高柱子一侧的柱子平移到另一边，其实是一样的，类似于下图的这种情况：

由于我们计算的是 水+柱子 的体积，因此对于一个位置 (pos) 它有意义当且仅当它比他左边或者右边的柱子高。

同时根据上图，我们可以发现其实所有柱子和水的体积之和就是两个次高柱子的高度。

那么我们可以先将所有的柱子从小到大枚举，每次插入一个次小值，然后枚举插入这个柱子后可以构成几个 水+柱子 的体积是这样高度的格子。

一个类似于背包的东西直接 bitset 维护即可。

code

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"RP++"<<endl
using namespace std;
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=5e2+10,M=25e3+10;
int n,cnt,sum,s[N];
bitset<M> bit[N],ans;
#undef int
int main()
{
	#define int long long
	freopen("drop.in","r",stdin); freopen("drop.out","w",stdout);
	n=read(); for(int i=1;i<=n;i++) s[i]=read(),sum+=s[i]; ans[sum]=true;
	sort(s+1,s+n+1,greater<int>()); bit[1][s[1]]=true;
	for(int i=2;i<=n;i++) bit[i]|=bit[i-1]<<s[2];
	for(int i=3;i<=n;i++) if(s[i]!=s[i-1])
	{for(int j=i;j<=n;j++) bit[j]|=bit[j-1]<<s[i];ans|=bit[n];}
	for(int i=sum;i<=M-10;i++) if(ans[i]) printf("%lld ",i-sum);
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的题解 P6345 [CCO 2017]接雨滴全部内容，希望文章能够帮你解决题解 P6345 [CCO 2017]接雨滴所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。