Uva：11401-Triangle Counting-白红宇

Uva：11401-Triangle Counting

阅读量：5093 次

发布时间：2019-06-13

本文共 1223 字，大约阅读时间需要 4 分钟。

Triangle Counting

Time limit1000 ms

Description

You are given n rods of length 1, 2…, n. You have to pick any 3 of them and build a triangle. How many distinct triangles can you make? Note that, two triangles will be considered different if they have at least 1 pair of arms with different length.

Input

The input for each case will have only a single positive integer n(1<=n<=1000000). The end of input will be indicated by a case with n<1. This case should not be processed.

Output

For each test case, print the number of distinct triangles you can make.

Simple Input

Simple Output

解题心得：

刚开始看到题的时候以为是以前做过的一个dfs的三角形拼接，但是这个题问的是用从1到n长度的木棍来拼接，然后比较容易就可以看出是一个递推的问题，每增添一根木棍答案就会增加一部分，然后就是怎么递推了。

这个递推的思想其实就是先算出所有能够选择的方案，然后减去重复的方案。从第一条边开始看有多少种方案，会发现是0+1+2+…..（x-2） = （x-1）*（x-2）/2。但是里面包含了不符合要求的，不符合要求的（两边之和不大于第三边）数量（n-1）/2，另外还有重复的，每个符合条件的情况算了两次（从前往后依次，从后往前一次），还要除2。

还可以按照组合数学来算，但是这样也挺麻烦的，好像还可以寻找循环节。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           using namespace std;const int maxn = 1000010;typedef long long ll;ll f[maxn];void pre_deal(){ for(long long i=4;i

转载于:https://www.cnblogs.com/GoldenFingers/p/9107194.html

你可能感兴趣的文章

【ul开发攻略】HTML5/CSS3菜单代码阴影+发光+圆角