这题 做出来真的好爽啊... it is cool although it is easy
虽然 已经是大概1 2点的事了 我拖到现在才写是因为------lol 终于赢一把了 ---
先贴下题目：
嗯 我一开始 用的是 3重for 我以为32767的数据量 是很小的.... 结果 TLE。。
OK 那么 我们只能换种方法了 看它里面的关系
假如 现在告诉你三角形的周长是 L 有个很重要又很基础的定理 --- 任意两条边之和大于第三边
你知道一个固定周长的三角形 最长边最短是在什么时候吗？ 那就是---- 等边三角形的时候 即 L/3 的时候
那么最大的时候呢？ 自然是L/2 的时候 这里我的（ L/2 )是不严密的 没有考虑 L的 奇偶性..
然后 我一开始的问题 就是出在这里了
因为当L为偶数的时候 L/2最长边 与 剩余的2边之和L/2 是相同的 这应该是排除的
当L为奇数的时候 L/2最长边 小于 剩余的2边之和（L/2+1） 这是成立的
这边 我们可以进行一个小处理之后就不用 把奇偶性分开考虑 假设 x 是最长边 那么x的范围就是
x -> L/3 ~ (L+1)/2 或 L/3 ~ (L-1)/2 第一个是< 第二个是<= 我个人还是喜欢第一种~
现在 我们已经完成了对于最长边的取值范围的剪枝
然后就是相对应的 当最长边取值为X时 剩余2条边的取值可能组合方案数 设剩余总和为y cnt为组合数
假设y为8 那么它有(1,7) (2,6),(3,5),(4,4)这4种可能- 设为z
但并不是直接加上就好 因为要考虑边的最大值问题与等边三角形问题
有一点 要知道 对于一个y 拆成2个正整数之和的方案是 y/2
那么z应该怎么考虑呢？
z-(y-x-1) 这里 我不知道怎么解释了 因为我当时是 写了几个式子 观察出来的-----但感觉 就是那么回事 可是 我解释不了啊 =-=
啰嗦了好多没用的话~ 上 code
1 #include <iostream> 2 using namespace std; 3 4 int main() 5 { 6 int n; 7 int cnt; 8 while( ~scanf("%d",&n) ) 9 { 10 cnt = 0; 11 for( int i = n/3+1 ; i<(n+1)/2 ; i++ ) 12 { 13 int j = n-i; 14 cnt = cnt + j/2 - (j-i-1); 15 } 16 printf( "%d\n",cnt ); 17 } 18 return 0; 19 }
原文：http://www.cnblogs.com/radical/p/3791241.html
