UVa 11401 Triangle Counting (计数DP)

题意:给定一个数 n,从1-n这些数中任意挑出3个数,能组成三角形的数目。

析:dp[i] 表示从1-i 个中任意挑出3个数,能组成三角形的数目。

代码如下:

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int Min(int a, int b){ return a < b ? a : b; }
inline int Max(int a, int b){ return a > b ? a : b; }
inline LL Min(LL a, LL b){ return a < b ? a : b; }
inline LL Max(LL a, LL b){ return a > b ? a : b; }
inline int gcd(int a, int b){ return b ? gcd(b, a%b) : a; }
inline int lcm(int a, int b){ return a * b / gcd(a, b); }
inline bool is_in(int r, int c){
    return r >= 0 && r < n && c >= 0 && c < m;
}
LL dp[maxn];

int main(){
    dp[3] = 0;
    for(int i = 4; i < maxn; ++i){
        if(i & 1)  dp[i] = dp[i-1] + (LL)(i-1)*((i-4)/2+1)/2;
        else dp[i] = dp[i-1] + (LL)((i-3)/2+1)*(i-2)/2;
    }
    while(cin >> n && n > 2){
        cout << dp[n] << endl;
    }
    return 0;
}
时间: 10-24

UVa 11401 Triangle Counting (计数DP)的相关文章

UVA 11401 - Triangle Counting(数论+计数问题)

题目链接:11401 - Triangle Counting 题意:有1,2,3....n的边,求最多能组成的三角形个数. 思路:利用三角形不等式,设最大边为x,那么y + z > x 得 x - y < z < x 然后y取取值,可以从1取到x - 1,y为n时候,有n - 1个解,那么总和为0 + 1 + 2 +...+ (x - 2) = (x - 1) * ( x- 2) / 2; 然后扣除掉重复的y = z的情况,在y > x / 2时,每个y取值会出现一次y = z.

UVA - 11401 - Triangle Counting (递推!)

UVA - 11401 Triangle Counting Time Limit: 1000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu Submit Status Description Problem G Triangle Counting Input: Standard Input Output: Standard Output You are given n rods of length 1, 2-, n. You have

uva 11401 - Triangle Counting(数论)

题目链接:uva 11401 - Triangle Counting 题目大意:有多少种方法可以从1,2,3...n中选出3个不同的数组成三角形,给出n,求种数. 解题思路:加法原理,设最大边为x的三角形有c(x)个,那么另外两条边长分别为y和z,根据三角形的形式可以的y+z>x,所以z的范围即为x?y<z<x 根据这个不等式可以得到每个y值所对应的z值个数,为等差数列,所以 c(x)=(x?1)?(x?2)2??x?12?2 然后根据递推:f(n)=∑i=1nc(i) 代码 #incl

【递推】【组合计数】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的情况,

UVA 11401 Triangle Counting

[题意分析] 本题就是在给定的N条边(边长是1,2,3,,,N)里面找合乎要求的三角形个数(任意两条边之和大于第三边).如果我们直接枚举合乎题意的三角形那么我们不太好出发(想想为什么?),那么我们可以采用补集观念,先找出不合乎要求的三角形数目,再用总的组合数减去不合乎要求的数目,就得最后的结果.那么问题是我们如何枚举不合乎要求的三角形数目呢?我们设三角形的三条边是a,b,c.我们不妨用c表示任意三条边中的边长最大值,那么我们可以得到一个简单的结论:如果能够构成三角形c<a+b.那么当用a和b作为

UVA 11401 - Triangle CountingTriangle Counting 数学

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

UVa 11401 - Triangle Countin

题目:给你n根长度分别为1,2,..,n的棍子,问能组成多少个不同的三角形. 分析:组合数学,计数原理.本题可以正向求解也可以反向求补集,这里采用正向求解. 1.首先写出前几组数据,找规律:{ 里面的括号是子情况 } (4,3,(2)) (5,4,(3,2)) (6,5,(4,3,2))(6,4,(3)) (7,6,(5,4,3,2))(7,5,(4,3)) (8,7,(6,5,4,3,2))(8,6,(5,4,3))(8,5,(4)) 对于上述的数据采用记号[a,b,c,...] 记录对应每种

UVA Triangle Counting 11401【几何+数学】

11401 - Triangle Counting Time limit: 1.000 seconds 题意:给你n个线段,长度1-n.问可以组成多少不同的三角形 解题思路: 设最大边长为x的三角形有C(x)个,另外两条边长分别为y和z,根据三角不等式有y+z>x.所以z的范围是x-y < z < x. ①根据这个不等式,当y=1时x-1 < z < x,无解:y=2时有一个解(z=x-1):y=3时有两个解(z=x-1或者z=x-2)--直到y=x-1时有x-2个解.根据等

Ant Counting POJ 3046(计数dp)

原题 题目链接 题目分析 计数dp题,感觉其实也可以用组合数学做,但我太菜了,推不出通用公式.dp可以定义dp[i][j]为前i种选j个蚂蚁有多少种选法,然后递推公式如下,其中c[i]表示第i种的数量, dp[i][j]=Σ(min(j,c[i]),k=0)dp[i-1][j-k].可以化简一下,dp[i][j]=∑(c[i],k=0)dp[i-1][j-1-k]+dp[i-1][j]-dp[i-1][j-1-c[i]],最后答案就是dp[t][s]+dp[t][s+1]+...+dp[t][b