每给定一个n,代表你有n根长度依次为1-n的棍子，求由这n根棍子可组成多少三角形

 

我们定义a[i]为最长边为i的三角形的数量，ans[i]为要输出的答案

显然ans[i + 1] = ans[i] + a[i + 1];

那么如何由a[i]求解a[i + 1]?

我们可以得到同时含有边i 和 i + 1的三角形数(i - 1 - 1)个

然后用长度为i + 1的棍子去取代长度为i的棍子得a[i]种情况

可当我们用长度为i + 1的棍子去取代长度为i的棍子，我们会发现原本(2, 4, 5)是可行的，而(2, 4, 6)不可

前两条的和比第三条大1时不可，所以我们多计数了第一条边为2～ i／2的数量，即i / 2 - 1种

故此递推式a[i + 1] = a[i] -(i / 2 - 1) + (i - 2) = a[i] + i - i / 2 - 1;

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define max(x, y) (x > y ? x : y) 7 #define min(x, y) (x > y ? y : x) 8 #define INF 0x3f3f3f3f 9 #define mod 100000000710 #define Yes printf("Yes\n")11 #define No printf("No\n")12 typedef long long LL;13 using namespace std;14 15 const int maxn = 1e6 + 10;16 LL a[maxn], ans[maxn];17 18 void init() {19     a[4] = 1; ans[4] = 1;20     for (int i = 5; i < maxn; i++) {21         a[i] = a[i - 1] + i - 2 - (i - 1) / 2;22         ans[i] = ans[i - 1] + a[i];23     }24 }25 26 int main(int argc, const char * argv[]) {27     init();28     int n;29     while (scanf("%d", &n), n >= 3) {30         printf("%lld\n", ans[n]);31     }32     return 0;33 }