首页 > 代码库 > 【递推】【组合计数】UVA - 11401 - Triangle Counting
【递推】【组合计数】UVA - 11401 - Triangle Counting
http://blog.csdn.net/highacm/article/details/8629173
题目大意:计算从1,2,3,...,n中选出3个不同的整数,使得以它们为边长可以构成三角形的个数。
思路:用一般的方法需要三重循环,时间复杂度为O(n^3),肯定超时,因此可用数学的方法对问题进行分析。设最大边长为x的三角形有c(x)个,另外两边长分别为y,z,则可得x-y<z<x;固定x枚举y,计算个数0+1+2+...+(x-2)=(x-1)(x-2)/2。上面的解包含了y=z的情况,而且其他情况算了两遍。而y=z的情况时y从x/2+1枚举到x-1为止有(x-1)/2个解,所以c(x)=((x-1)*(x-2)/2-(x-1)/2)/2。
由以上分析可得,最大边长不超过n的三角形数目为f(n)=c(1)+c(2)+...+c(n)。
#include<cstdio> #include<iostream> using namespace std; typedef long long ll; ll f[1000010]; int n; int main(){ for(int i=4;i<=1000000;++i){ f[i]=f[i-1]+((ll)(i-1)*(ll)(i-2)/2ll-(ll)((i-1)/2))/2ll; } while(1){ scanf("%d",&n); if(n<3){ break; } cout<<f[n]<<endl; } return 0; }
【递推】【组合计数】UVA - 11401 - Triangle Counting
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。