HDU 2050折线分割平面（递推）

喜欢ヅ旅行 2022-05-25 03:38 142阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <span style="margin-right:20px;"></span> 
    </div></td> 
  </tr> 
  <tr> 
   <td align="center"><h1 style="color:#1a5cc8;">折线分割平面</h1><strong><span style="font-size:12px;font-family:Arial;color:#008000;">Time Limit: 2000/1000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 65536/32768 K (Java/Others)<br>Total Submission(s): 36479&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 24442<br></span></strong><br><br> 
    <div>
      Problem Description 
    </div> 
    <div>
      我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。 
     <br> 
     <img src="http://acm.hdu.edu.cn/data/images/C40-1008-1.jpg" alt=""> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Input 
    </div> 
    <div>
      输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0&lt;n&lt;=10000),表示折线的数量。 
     <br> 
     <br> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Output 
    </div> 
    <div>
      对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。 
     <br> 
     <br> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Sample Input 
    </div> 
    <div> 
     <pre></pre> 
     <div style="font-family:'Courier New', Courier, monospace;">
       212 
     </div> 
    </div> 
    <div>
      &nbsp; 
    </div> 
    <div>
      Sample Output 
    </div> 
    <div> 
     <pre></pre> 
     <div style="font-family:'Courier New', Courier, monospace;">
       27 
     </div> 
    </div> 
    <div>
      &nbsp; 
    </div></td> 
  </tr> 
 </tbody> 
</table>

公式

f(n) = 2*n*n-n+1

/*
    	f(n) = 2*n*n-n+1
    */
    
    #include<cstdio>
    int main()
    {
    	int t,n;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		printf("%d\n",2*n*n-n+1);
    	}
    	return 0;
    }