题目链接：

KK's Point

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Our lovely KK has a difficult mathematical problem:He points N(2≤N≤10^5) points on a circle,there are all different.Now he's going to connect the N points with each other(There are no three lines in the circle to hand over a point.).KK wants to know how many points are there in the picture(Including the dots of boundary).

Input

The first line of the input file contains an integer T(1≤T≤10), which indicates the number of test cases.

For each test case, there are one lines,includes a integer N(2≤N≤10^5),indicating the number of dots of the polygon.

Output

For each test case, there are one lines,includes a integer,indicating the number of the dots.

Sample Input

Sample Output

题意：

在圆上有n个点,每两个点都相连,问连线有多少个交点,任意三根线不交于同一点;

思路：

dp来解决,每加入一个点我们可以发现,增加的交点个数为1*n+2*(n-1)+3*(n-2)+...+n*1+1(最后这个1是这个点本身);

这是怎么来的可以画个图来自己画一下看看;每次把原先的点分成两拨;

现在的问题变成怎么求上述的式子了;

f(n)=1*n+2*(n-1)+3*(n-2)+...+n*1;

f(n+1)=1*(n+1)+2*n+3*(n-1)+...+(n+1)*1;

f(n+1)-f(n)=(n+1)+n+(n-1)+(n-2)+...+1=(n+1)(n+2)/2;

那么状态转移方程就有了dp[i]=dp[i-1]+1+f(i-3);

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

using namespace std;

typedef long long ll;

const ll mod=1e9+;

const ll inf=1e15;

const int N=1e5+;

int n;

ll dp[N],f[N];

void fun()

{

    dp[]=;//注意dp[1]   dp[2]的初始化,我在这里就wa了一发;

    dp[]=;

    dp[]=;

    f[]=;

    for(int i=;i<N;i++)

    {

        ll x=(i);

        f[i]=f[i-]+x*(x+)/;

    }

    for(int i=;i<N;i++)

    {

        dp[i]=dp[i-]++f[i-];

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    fun();

    while(t--)

    {

        scanf("%d",&n);

        cout<<dp[n]<<"\n";

        //printf("%lld\n",dp[n]);

    }

    return ;

}

巴特西

hdu-5621 KK's Point(dp+数学)

KK's Point

最新文章

热门文章