这道题目暴力的话是会超时的，所以我们想到数学优化：正难则反。
我们先求出所有方案数再减去不合法的就是合法的方案数。
首先总方案数比较好求用隔板法，就是我们将 L 分给不同的三个数，可以不分给一个数，那么为了解决可以不分给一个数的情况，我们可以将 L 加 3 加上的这三个可以理解为“假的”也就是你分到了这“假的”数，你的数值是不会增加了，然后我们要分给 3 个数，方案数就是： C^3_{L+3} 。
那么，不合法的数呢？大家都知道三角形两边之和大于第三边，于是我们可以得出三种不合法情况 (a+x)≥(b+y)+(c+z) 和 (b+y)≥(a+x)+(c+z) 和 (c+z)≥(a+x)+(b+y) 这里的 x,y,z 分别表示给 a,b,c 加上的数。
接下来我们以 (a+x)≥(b+y)+(c+z) 为例：我们可以变换一下不等式也就变成了 x ≥ y+z + (b+c-a) 这个时候会分成两种情况：
- k = b+c-a ≥ 0 这个时候 k 为非负数直接枚举 y+z 的值。
- 当 k＜0 这个时候条件变成 x ≥ y+z - |k| 这个时候我们需要分块处理。
好了，现在就可以写出大体代码框架了：
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
#define int long long
I AK IOI;
int a,b,c,l,sum,ans;
int check1(int L,int k){
/*当k为非负数的时候*/
}
int check2(int L,int k){
/*当k为负数的时候*/
}
int f(int k,int L){
if(k>=0){
if(L<k)return 0;//如果L小于K直接返回 0
else return check1(L,k);当k为为负数时枚举k+z
}
else return check2(L,-k);//当k为负数的时候分成2快理
}
signed main(){
/*输入*/
sum=(l+3)*(l+2)*(l+1)/6;//总方案数 C^{3}_{L+3}
int k1=b+c-a,k2=a+c-b,k3=a+b-c;
int sum1=f(k1,l),sum2=f(k2,l),sum3=f(k3,l);//三种不合法的情况的数目
ans=sum-(sum1+sum2+sum3);//容斥原理这就是最后的答案
/*输出*/
i_ak ioi;
}
分析一下复杂度：
- 时间复杂度： O(L) 不会超市！放心提交！
- 空间复杂度： O(1) 没有额外空间。