天天看點

動态規劃—Problem N

動态規劃—Problem N

題意

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

動态規劃—Problem N

解題思路

遞推。先分析下直線分割平面的情況,增加第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 ;
}