题目大意:
a,b,c三根木棍可以增加三个不同的数字,aa,bb,cc,且aa+bb+cc<=L,问能构成三角形的木棒有多少种方案
题目思路:
如果我们直接考虑把L分配给aa,bb,cc好像不好下手
所以逆向考虑
合法的情况 = 所有情况 - 不合法的情况
step1:
首先计算所有的情况
假设L当时为l
我们把长度为l分配去的总的方案
这个问题我们等效为:有三个篮子,每个篮子放至少一个个物品,总共l个物品,问有多少种方案
我们用插板法解决这个问题
因为每个篮子放至少一个,而我们的目标是可以放0个,怎么办呢?
我们可以增加几个物品使初始每个篮子中就有一个,这里假设有m个篮子,n个物品
那我们的物品个数变为n+m,这时候会产生n+m-1个隔板
然后我们要选出m部分来,也就是放m-1个隔板
此时的方案为C(n+m-1,m-1)
回到这个题目
此时长度为l时,方案为C(l+3-1,3-1)
然后我们枚举一遍l,求和算出总的方案
所以得到为l的时候方案为C(l+2,2)
step2:
求不合法的方案==
假设a+aa,b+bb,c+cc(aa,bb,cc分别为分配的增加的长度)
假设a+aa是那条最长的边
此时不合法需要满足如下条件:
b+bb+c+cc<=a+aa
bb+cc<=l-aa
得
bb+cc<=min(l-aa,a-b-c+aa)
令T=bb+cc
这个时候再进行一下问题转化
有T个物品,分配到三个篮子里(可以分配0个)
三个篮子分别是bb,cc和多余的部分
回到上面的插板法一样的解法C(t+3-1.3-1)
然后用总的减去不合法就ok了
CODE:
ll b,c,a,l; int main() { a=read(),b=read(),c=read(),l=read(); ll zong = (l+1)*(l+2)*(l+3)/6ll; ll no; for(int aa=0 ; aa<=l ; aa++) { ll t = min(l-aa,a-b-c+aa); if(t<0) continue; no = (t+2)*(t+1)/2ll; zong-=no; } for(int bb=0 ; bb<=l ; bb++) { ll t = min(l-bb,b-a-c+bb); if(t<0) continue; no = (t+2)*(t+1)/2ll; zong-=no; } for(int cc=0 ; cc<=l ; cc++) { ll t = min(l-cc,c-b-a+cc); if(t<0) continue; no = (t+2)*(t+1)/2ll; zong-=no; } out(zong); return 0; }