动态规划 专题

HDU 2050 折线分割平面

题目描述

输入输出样例

思路

仔细分析一下题目，关键是找到递推关系。折角的地方、射线只能分隔出一个平面，线段可以分出两个平面。

递推关系如下：

dp[i] = 2*i*i-i+1;

可以直接打表。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int dp[10010];

int main(){
	int n;
	memset(dp,0,(sizeof(dp)));
	dp[1] = 2;
	dp[2] = 7;
	for(int i = 3; i <= 10010; ++i){
		dp[i] = 2*i*i-i+1;  //递推关系，折角的地方、射线只能分隔出一个平面，线段可以分出两个平面 
	} 
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i){
		int num;
		scanf("%d", &num);
		printf("%d\n", dp[num]);
	}
	return 0;
}