2022信息与未来预备刷题1《New Online Judge 1112: 平面分割》

P1112 - 平面分割 - New Online Judgehttp://oj.ecustacm.cn/problem.php?id=1112

内存限制：256 MB时间限制：1 S标准输入输出

题目类型：传统评测方式：文本比较上传者：外部导入

提交：157通过：121

提交提交记录统计讨论版

题目描述

同一平面内有n（n≤500）条直线，已知其中p（p≥2）条直线相交于同一点，则这n条直线最多能将平面分割成多少个不同的区域？

输入格式

两个整数n（n≤500）和p（2≤p≤n）

输出格式

一个正整数，代表最多分割成的区域数目。

输入样例 复制

12 5

输出样例 复制

73

分类标签

 基础题 动态规划

思路：

公式

int f[N];
f[p]=2*p;
for(int i=p+1;i<=n;i++)f[i]=f[i-1]+i; 

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int> 
#define vll vector<ll> 
#define vll2 vector<ll,vector<ll> > 
#define vi2 vector<int,vector<int> > 
#define pii pair<int,int>
#define pll pair<ll,ll>
int main(){
	
	int p,n;
	cin>>n>>p; 
	vi v(n+5);
	for(int i=0;i<v.size();i++) v[i]=0;
    v[p]=2*p;
	for(int i=p+1;i<n+1;i++) v[i]=v[i-1]+i;
	cout<<v[n];                                                                                                                                                                                                                              
    return 0;
}
//ACplease!!!


/*  printf("                                                                \n");
	printf("                                                                \n");
	printf("       * * *               * * *             * * *             * * *            \n");
	printf("     *       *           *       *         *      *          *       *         \n");
	printf("    *        *          *         *       *        *        *         *        \n");
	printf("            *           *         *                *                  *      \n");
	printf("           *            *         *               *                  *     \n");
	printf("          *             *         *              *                  *       \n");
	printf("         *              *         *             *                  *            \n");
	printf("        *               *         *           *                  *            \n");
	printf("      *                  *       *          *                  *           \n");
	printf("    * * * * * * *          * * *          * * * * * * *      * * * * * * *                           \n");
*/