数学问题 递推

设三角形三边长分别为x,y,z,满足x>y>z

可以得出x-y<z<x

当x=n时：

　　当y=1时无解；当y=2时有一个解；当y=3时有2个解....当y=n-1时有n-2个解。

　　总共有 (n-1)(n-2)/2个解。

　　减去其中的 (x-1) div 2 个等腰三角形，剩下的三角形每个都被算了两遍(因为计算时y和z大小关系未定)

 

那么，x=n时，方案数f[x]=f[x-1](//最长边为x-1的方案数) + ((n-1)(n-2)/2-(x-1)/2)/2  (//最长边为x的方案数)

递推出解。

 

1 /*by SilverN*/ 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #define LL long long 8 using namespace std; 9 const int mxn=1000010;10 LL s[mxn];11 int main(){12     LL i,j;13     for(i=3;i
          
           =3){17 printf("%lld\n",s[n]);18 }19 return 0;20 }