首页 > 代码库 > 51Nod 1509 加长棒（隔板法）
51Nod 1509 加长棒（隔板法）
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1509
思路：
直接去解可行的方法有点麻烦，所以应该用总的方法去减去不可行的方法，有点像容斥原理。
将加长棒分成4个部分，允许为0，其中一部分表示剩余。这个就是经典的隔板法了。
这是百度百科上的一个例子，看完之后应该就理解隔板法的做法了吧。
这道题目也就是要将L分成4部分，允许为空，所以先L+4，表示每个部分至少为1，所以总共有L+4-1的空隙可以插板，我们需要插3个板，所以总的方法数为C（L+4-1,3）。
接下来求解不满足的个数:
构不成三角形的条件就是（假设c为最大边）：a+x+b+y<=c+z
同时还满足：x+y+z<=L
所以x+y<=min（c+z-a-b，l-z）
接下来我们只需要枚举z，然后求出x+y的值，把它的长度加到两根棒上，可以为0也可以剩余，这不就又是前面的隔板法了吗。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 10 typedef long long LL;11 12 LL a,b,c,l;13 14 LL solve(LL a,LL b, LL c, LL l) //设c为最大边15 {16 LL cnt=0;17 for(int z=0;z<=l;z++)18 {19 LL x=min(c+z-a-b,l-z);20 if(x>=0) cnt+=(x+1)*(x+2)/2;21 }22 return cnt;23 }24 25 int main()26 {27 //freopen("D:\\input.txt","r",stdin);28 while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&l))29 {30 LL ans=(l+1)*(l+2)*(l+3)/6;31 ans-=solve(a,b,c,l);32 ans-=solve(a,c,b,l);33 ans-=solve(b,c,a,l);34 printf("%lld\n",ans);35 }36 }
51Nod 1509 加长棒（隔板法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。