HDU 1290: 항 전 50 주년 개교 기념일 선물 [수학]

항 전 50 주년 개교 기념일 에 바 치 는 선물
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9353    Accepted Submission(s): 5199
Problem Description
혹시 불평 이 많 았 나 봐 요.
어쩌면 너 는 여전히 슬픔 을 품 고 있 을 지도 모른다
어쩌면 너 는 지척 에 있 을 지도 모른다
그렇게 지도 모른다, 아마, 아마...
모든 학생 들 에 게
모교
영원히
생명의 바다
올 해 는 우리 항 전 개교 50 주년 인 데, 이것 은 축복 할 만 한 날 이다.우 리 는 모교 에 어떤 선물 을 주어 야 합 니까?지금 여러분 들 에 게 가장 좋 은 선물 은 당연히 성 경기 의 좋 은 성적 입 니 다. 저 는 시합 에 참가 할 수 없습니다. 학교 에 DOOM III 구형 큰 케이크 를 드 리 겠 습 니 다. 이것 은 명 품 입 니 다. 제 가 반년 동안 돈 을 써 야 할 것 같 습 니 다.
정식 개교 기념일 을 상상 하 며 교장 선생님 이 직접 칼 을 휘 두 르 고 이 큰 케이크 를 각지 에서 축하 하 러 온 학우 들 에 게 나 누 어 주 셨 으 니 모두 기뻐 하 실 거 예요. 하하, 침 흘 렸 죠?
잠시 만 요. 케이크 를 먹 기 전에 여러분 의 질문 을 받 겠 습 니 다. 만약 에 교장 선생님 께 서 케이크 에 N 칼 을 자 르 셨 다 면 (교장 선생님 의 칼질 이 아주 좋 고 모든 칼 이 절대적 인 평면 입 니 다) 이 구형 케이크 를 최대 몇 조각 으로 자 를 수 있 습 니까?
이 문 제 를 풀 수 없어, 케이크 먹 을 게 없어!
위 - 위 - 모 - 교 -, 위 - 위 - 알 - 떡 - (DGMM 을 위 한 것 이 아니 라 단풍 의 날개 가 가장 떠 오 르 는...), 플러스 - 오 일 -!
 
Input
입력 데 이 터 는 여러 개의 테스트 인 스 턴 스 를 포함 하고 모든 인 스 턴 스 는 한 줄 을 차지 하 며 줄 마다 정수 n (1 < = n < = 1000) 을 포함 하여 자 른 칼 수 를 표시 합 니 다.
 
Output
각 조 의 입력 데 이 터 는 해당 하 는 케이크 블록 수 를 출력 하고 테스트 인 스 턴 스 마다 한 줄 을 출력 하 십시오.
 
Sample Input

   
   
   
   

    
    
    
    1
2
3
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    2
4
8
   
   
   
   

 
Author
lcy
 
2 차원 의 분할 문 제 를 통 해 알 수 있 듯 이 평면 분할 은 선 간 의 교점 과 관계 가 있다. 즉, 교점 은 방사선 과 선분 의 수 를 결정 하고 새로 추 가 된 구역 수 를 결정 한다.3 차원 에서 평면 적 인 교차 선 과 관계 가 있 는 지 생각해 보 세 요.n - 1 개의 평면 이 있 을 때 분 단 된 공간 수 는 f (n - 1) 이다.가장 많은 공간 수 를 가 지 려 면 n 번 째 평면 은 앞의 n - 1 평면 과 교차 해 야 하고 공 통 된 교차 선 이 있어 서 는 안 된다.최대 n - 1 교차 선.이 n - 1 개의 교차 선 은 n 개의 평면 을 최대 g (n - 1) 개의 구역 으로 나 누 었 다.(g (n) 은 (1) 의 직선 분할 평면 개수) 이 평면 은 기 존의 공간 을 둘 로 나 누 면 최대 g (n - 1) 개의 공간 을 증가 합 니 다.
그러므로 f = f (n - 1) + g (n - 1) ps:g(n)=n(n+1)/2+1
=f(n-2)+g(n-2)+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
AC—code：

#include<cstdio>
int main()
{
	int i,n,f[1005],g[1005];
	f[1]=2;
	g[1]=2;
	for(i=2;i<=1005;i++)
		g[i]=g[i-1]+i;
	for(i=2;i<=1005;i++)
		f[i]=f[i-1]+g[i-1];
	while(~scanf("%d",&n))
		printf("%d
",f[n]);
	return 0;
}