HDU-2050

2018-12-24  本文已影响0人  Caproner

首先,对于这种输入和输出均只有一个数的,那么首先需要想到的就是数列
那么,问题就是输入n,如何求数列的第n项。
这个从高中的知识就可以得到,要么找递推公式,要么找通项公式。
不过事实上找通项公式的难度一般远大于找递推的,所以我们遇到这种问题首先想的就是找递推公式。
递推公式的话,那么其基本思想就是从前面的一个状态推到当前的状态。
好的,于是问题就变成,现在给出有n条折线的最优划分方案,问再加一条的话最优划分方案是多少。
在此之前我们先规定在平面内永远都不要做两条平行的线,这个显然可以做到。
首先考虑在有两条折线的时候的情况:

image
那么这里面有几个区域就很好数了,一共是7个。
那么第三条折线怎么画是最优的呢?在这之前我把问题转化为做两条起点相同的射线。
首先我们知道所有的线都两两不平行。也就是说我可以做一条跟他们都不平行的线来跟他们都相交
那么在这个图里,就有4条线,于是我们先做第一条射线。我们的目标是令其跟已知的所有线都相交。于是就可以这么做:
image
这条射线经过了4条线,一共被分为5小段,除了最靠近射线起点的那一段之外剩下的每一段都割开了一个区域。
那么同理的,我也可以从同个起点出发,再做一条与4条线相交的射线:
image.png
那么类似的,我同样得到了5个线段,除了最靠近射线起点的那一段之外剩下的每一段都割开了一个区域。
还有就是,靠近射线起点的两条线段组成一个小折线,又可以割出一块。
好了,于是我们就可以知道,做第三条折线一共可以割出4+4+1块。
接着我们把情况推到n条折线。当然前面的假设还是成立的,就是两两不平行的情况。
那么显然的,我可以做一条射线使其跟所有的2n条线相交,并割出2n个区域;然后再在这条射线的起点上再做一条射线,再割2n个区域,最后射线的起点端的两个小线段围住一块区域,再得到一个区域。
于是我们就可以得到这样一个结论。n+1条折线分割的区域会比n条折线分割的区域多4n+1个
那么我们假设答案是f(n)的话,那么递推式就是:f(n+1)=f(n)+4n+1
代码如下:
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL ans[10005];

void init()
{
    ans[1]=2;
    for(int i=1;i<=10000;i++)
    {
        ans[i+1]=ans[i]+4*i+1;
    }
}

int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("%lld\n",ans[n]);
    }
    return 0;
}
上一篇下一篇

猜你喜欢

热点阅读