HDU 1290平面分割空間

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1290
解析:直線分割平面を参照すると,平面分割は線間の交点個数,すなわち交点が分割する線分と線の本数を決定し,線分と線の本数が分割する平面数を決定することを知ると,3次元空間に対応し,空間分割は平面の交線数に関係するはずであることが容易に考えられるが,事実も同様である.n-1個の平面がある場合、分割された空間数はf(n-1)であり、n番目の平面が最も多くの空間数を分割するには、前のn-1個の平面と交差し、重複しない交線が必要であり、このn-1本の交線は同時にn番目の平面をg(n-1)個の領域(g(n)がn本の直線分割平面の最大数)に分割する.これらの領域は元の空間を2つに分け、g(n−1)は増加した空間数=>f(n)=f(n−1)+g(n−1)であり、g(n)=g(n−1)+nである.
さらに簡略化すると、式は次のようになります.
f(n)=f(n-1)+g(n-1)
      =f(n-2)+g(n-1)+g(n-1)
      ......
      =f(1)+g(1)+g(2)+...+g(n-1)
      =2+(1*2+2*3+3*4+……+(n-1)n)/2+(n-1)
      =(1+2^2+3^2+4^2+……+n^2-1-2-3-……-n )/2+n+1
      =(n^3+5n)/6+1
実装コードは次のとおりです.

#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
    int f[10001],p[10001];
    int n,i;
    p[1]=2;
    f[1]=2;
    for(i=2;i<=10000;i++)
      p[i]=p[i-1]+i;
    for(i=2;i<=10000;i++)
      f[i]=f[i-1]+p[i-1];
    while(scanf("%d",&n)!=-1)
      printf("%d
",f[n]);
    return 0;
}