题目大意：
有n根连续的木棒，其中有m根是坏的，现在要求将木棒切成连续的四段，使得其中三段中都不包含坏的木棒，且三段木棒的长度和最大，在最长的前提下看这三段木棒能否拼成三角形，如果能的话，问最多有多少种且木棒的方法
解题思路：要使三段都不含坏的木棒，就要把所有坏的木棒包含在一段里，就要找出坏的木棒的最小位置和最大位置，然后往这两处进行切割，这样就分成三段了，找出最长的那段再进行切割，再判断能否组成三角形即可(这是一般情况)
特殊情况下，坏的木棒是在第一根和最后一根，这要进行特殊处理
1。如果坏的木棒有第一根和最后一根，那么答案就是0了
2。如果第一根坏了且最后一根没坏，那么就找到最大的那根坏的木棒的位置进行切割，这样就剩下一段好的了
3。如果最后一根坏了且第一根没坏，那么就找到最小的那根坏的木棒的位置进行切割
考虑一下只剩一段如何求切割方法，这里借用了一下别人的图
枚举x1，由组成三角形的条件可得
x1 + n - x1 - x2 > x2,即 n / 2 > x2
x1 + x2 > n - x1 - x2,即x2 > n / 2 - x1
x2 + n - x1 - x2 > x1,即n / 2 > x1
有上面可得 n / 2 -x1 < x2 < n / 2
因为是小于而不是小于等于(例子是n＝4，x1 ＝ 1的时候)，所以上面的式子要改为n / 2 - x1 < x2 < (n+1) / 2
所以只要枚举所有的x1,求出x2,就是所有的切割方法了
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define maxn 1010 6 7 int main() 8 { 9 int n ,m; 10 while(scanf("%d%d", &n, &m) == 2) 11 { 12 int Min = n + 1, Max = -1, pos; 13 for(int i = 0; i < m; i++) 14 { 15 scanf("%d", &pos); 16 Min = min(Min,pos); 17 Max = max(Max,pos); 18 } 19 20 if(Min == 1 && Max == n) 21 { 22 printf("0 "); 23 continue; 24 } 25 26 int len1, len2; 27 len1 = Min - 1; 28 len2 = n - Max; 29 30 if(len1 > len2) 31 swap(len1,len2); 32 33 int L , R; 34 if(Min == 1 || Max == n) 35 { 36 long long ans = 0; 37 for(int i = 1; i < n; i++) 38 { 39 if(i >= len2 - i) 40 break; 41 42 L = (len2 ) / 2 - i; 43 R = (len2 + 1) / 2; 44 ans += (R - L - 1); 45 } 46 printf("%I64d ",ans); 47 continue; 48 } 49 else 50 { 51 long long ans = 0; 52 int t; 53 //printf("%d %d ",len1,len2); 54 for(int i = 1; i < len2; i++) 55 { 56 t = len2 - i; 57 if(len2>len1&&len1 + 2 * i > len2 && len1 + len2 > 2 * i) 58 ans++; 59 } 60 printf("%I64d ",ans); 61 } 62 } 63 return 0; 64 }