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也可以剩余,这不就又是前面的隔板法了吗。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
using namespace std; typedef long long LL; LL a,b,c,l; LL solve(LL a,LL b, LL c, LL l) //设c为最大边
{
LL cnt=;
for(int z=;z<=l;z++)
{
LL x=min(c+z-a-b,l-z);
if(x>=) cnt+=(x+)*(x+)/;
}
return cnt;
} int main()
{
//freopen("D:\\input.txt","r",stdin);
while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&l))
{
LL ans=(l+)*(l+)*(l+)/;
ans-=solve(a,b,c,l);
ans-=solve(a,c,b,l);
ans-=solve(b,c,a,l);
printf("%lld\n",ans);
}
}