動态規劃—Problem N

動态規劃—Problem N

題意

我們看到過很多直線分割平面的題目，今天的這個題目稍微有些變化，我們要求的是n條折線分割平面的最大數目。比如，一條折線可以将平面分成兩部分，兩條折線最多可以将平面分成7部分，具體如下所示。

解題思路

遞推。先分析下直線分割平面的情況，增加第n條直線的時候，跟之前的直線最多有n-1個交點，此時分出的部分多出了（n-1）+1；折線也是同理，f(1)=2,f(2)=7,先畫好前面n-1條折線，當增加第n條拆線時，此時與圖形新的交點最多有2*2（n-1）個，是以分出的部分多出了2*2（n-1）+1。是以推出：

f(n)=f(n-1)+4*(n-1)+1（n>=3）

感想

先吐槽下，又沒有圖檔，那怎麼做？？隻好百度找原題了。方法嘛，遞推遞推喽，呵呵。

AC代碼

#include<iostream>
using namespace std;
#define MAX 10010
int main()
{
    long long int  dp[MAX]; 
    int T,n;
    cin>>T;
    while(T--)
    {
        dp[]=;
        cin>>n;
        int i;
        for(i=;i<=n;i++)
            dp[i]=dp[i-]+*(i-)+;
        cout<<dp[i-]<<endl;
    }
    return ;
}