合唱隊(duì)形chorus——NOIP(全國(guó)青少年信息學(xué)奧林匹克聯(lián)

1、合唱隊(duì)形 解題報(bào)告<問(wèn)題描述> N位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。    合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1，2，K，他們的身高分別為T(mén)1，T2，TK，  則他們的身高滿足T1<.<Ti>Ti+1>>TK(1<=i<=K)。    你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。- 輸入文件  &#

2、160; 輸入文件chorus.in的第一行是一個(gè)整數(shù)N(2<=N<=100)，表示同學(xué)的總數(shù)。第一行有n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)Ti(130<=Ti<=230)是第i位同學(xué)的身高(厘米)。- 輸出文件    輸出文件chorus.out包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列。- 樣例輸入8186 186 150 200 160 130 197 220- 樣例輸出4- 數(shù)據(jù)規(guī)模對(duì)于50的數(shù)據(jù)，保證有n<=20；對(duì)于全部的數(shù)據(jù)，保證有n<=100。<算法分析>動(dòng)態(tài)規(guī)劃。最基本

3、的想法是：枚舉中間最高的一個(gè)人，接著對(duì)它的左邊求最長(zhǎng)上升序列（注意序列中最高的同學(xué)不應(yīng)高過(guò)基準(zhǔn)），對(duì)右邊求最長(zhǎng)下降序列（同樣的，序列中最高的同學(xué)不應(yīng)高過(guò)基準(zhǔn)）。時(shí)間復(fù)雜度為O(n3)，算法實(shí)現(xiàn)起來(lái)也很簡(jiǎn)單。接著對(duì)這個(gè)算法進(jìn)行分析，我們不難發(fā)現(xiàn)，假如還是基于枚舉一個(gè)同學(xué)的話，設(shè)Incsqi表示了1 - i的最長(zhǎng)上升序列，Decsqi表示了i - n的最長(zhǎng)下降序列，那么，Currenti = Incsqi + Decsqi - 1（兩個(gè)數(shù)組中i被重復(fù)計(jì)算了）那么，我們只需要先求好最長(zhǎng)上升和下降序列，然后枚舉中間最高的同學(xué)就可以了。<算法優(yōu)化>求最長(zhǎng)上升序列的經(jīng)典狀態(tài)轉(zhuǎn)移方程為：opti

4、 = maxoptj+1, 其中i<j<=n, 且listj>listi我們對(duì)狀態(tài)轉(zhuǎn)移方程稍微做一些修改：opti = maxopti+1, minj, recj>=listirecj = listi很明顯可以看出，在opti的尋找j的過(guò)程當(dāng)中，查詢序列是單調(diào)的，于是可以用二分法，就十分巧妙地在logn的時(shí)間內(nèi)找到指定的j，而問(wèn)題的總體復(fù)雜度為O(nlogn)。這樣，這個(gè)問(wèn)題的算法效率就得到了大幅度的提升，即便n是106，也可以輕松應(yīng)對(duì)。<代碼清單>#include <fstream>#include <cstring>using n

5、amespace std;ifstream fin("chorus.in");ofstream fout("chorus.out");const int maxn = 100;int n, amaxn;int incsqmaxn, decsqmaxn;void init() fin >> n;for (int i = 0; i < n; i +)fin >> ai;void LIncSeq()int i, low, high, mid, ans = 0;int solmaxn;for (i = 0; i < n; i

6、+) low = 1; high = ans;while (low <= high) mid = (low + high) >> 1;if (solmid < ai) low = mid + 1;else high = mid - 1;if (low > ans) ans +;sollow = ai;incsqi = ans;void LDecSeq()int i, low, high, mid, ans = 0;int solmaxn;for (i = 0; i < n; i +) low = 1; high = ans;while (low <=

7、high) mid = (low + high) >> 1;if (solmid > ai) low = mid + 1;else high = mid - 1;if (low > ans) ans +;sollow = ai;decsqi = ans;void work() int i, max = 0;LIncSeq();LDecSeq();for (i = 0; i < n; i +)if (incsqi + decsqi - 1 > max)max = incsqi + decsqi - 1;fout << n - max << endl;int main() init();work();return 0;&