tv講義noi2006準(zhǔn)備1-dp2006動(dòng)態(tài)天津模擬day1problem

1、NOI2006 模擬Day 1測(cè)試時(shí)間：5 個(gè)小時(shí)任務(wù)ABC任務(wù)名稱回文序列設(shè)計(jì)最大的多邊形主文件名palin.cpp/paschip.cpp/paspolygon.cpp/pas可執(zhí)行文件名palin.exechip.exepolygon.exe輸入文件名palin.inchip.inpolygon.in輸出文件名palin.ohip.outpolygon.out測(cè)試點(diǎn)數(shù)101020時(shí)間限制3sec per test2sec per test0.5sec per test可用內(nèi)存128 MBytes128 MBytes32 MBytes回文序列任務(wù)描述給定一個(gè)字符串 S，一次操作被定義為交換

2、相鄰的兩個(gè)字母。例如將 ABC 經(jīng)過(guò)一次操作可以變?yōu)锳CB。的目標(biāo)是使用最少的交換次數(shù)將給定字符串 S 變成一個(gè)回文串。所謂的回文串就是從前往后讀與從后往前讀相同的字符串。例如 MAMAD 可以通過(guò) 3 次交換操作就可以變成一個(gè)回文：MAMAD MAMDA MADMA MADAM輸入格式輸入文件第一行為一個(gè)整數(shù) T ，表示數(shù)據(jù)組數(shù)。接下來(lái) T 行，每行包含一個(gè)整數(shù) N 和一個(gè)長(zhǎng)度為 N 的字符串S。 N 和S 之間用一個(gè)空格隔開,保證不會(huì)有多余空格.輸出格式對(duì)于每一行輸入輸出一行信息：如果不能通過(guò)若干變換使 S 變成回文串,則輸出Im出最少的操作次數(shù).sible!(不包括引號(hào)),否則輸規(guī)模對(duì)于

3、 30%的數(shù)據(jù), 滿足 N = 1000對(duì)于 100%的數(shù)據(jù),滿足 N = 100000對(duì)于所有數(shù)據(jù), T 都不超過(guò) 10設(shè)計(jì)任務(wù)描述一個(gè)正方形在這個(gè)平板放置在直角坐標(biāo)系中，且上面標(biāo)出了一些點(diǎn)（元件），的左下角恰好為直角坐標(biāo)系的原點(diǎn)。的目標(biāo)就是把每個(gè)標(biāo)出的點(diǎn)都水平或，所以任何一條連線（從一個(gè)標(biāo)記點(diǎn)到者豎直地連接到平板的某條邊上。由于這是一個(gè)平板的邊界這條線）都不應(yīng)該包含另一個(gè)標(biāo)記點(diǎn)；并且任何兩條連線都不能相交。請(qǐng)你寫一個(gè)程序求出一種連線的方案，使得這些線的長(zhǎng)度之和盡量小。輸入格式第一行一個(gè)整數(shù) A（2 A 30），表示正方形平板的邊長(zhǎng)。第二行一個(gè)整數(shù) N（2 N 100），表示平板上標(biāo)記點(diǎn)的數(shù)

4、目。接下來(lái) N 行，每行兩個(gè)數(shù) x , y（1 x , yA - 1）輸出格式僅輸出一行：表示所有連線的長(zhǎng)度總和。如果無(wú)解，只需要輸出一個(gè)- 。輸入樣例輸入樣例4最大的多邊形任務(wù)描述Timothy 有一塊圓形的鏡子，但是鏡子的周邊（周長(zhǎng)）受到了污染，十分影響美觀，因此 Timothy 打算把這塊鏡子修剪成為一個(gè)多邊形，這樣就會(huì)去除所有的周長(zhǎng)：不錯(cuò)的主意！Tim 有一臺(tái)專業(yè)的玻璃切割機(jī)，可以輕松并且漂亮的把一塊玻璃分成兩半：當(dāng)然是沿著一條直線。但是這面鏡子卻很厚，質(zhì)地也很堅(jiān)硬，若是隨意的去切難免會(huì)損壞切割機(jī)。因此Tim 在鏡子的邊緣選擇了 N 個(gè)密度相對(duì)較小的位置，若是從這些地方下刀，系數(shù)就小多了。然而由于技術(shù)原因，Tim 最多只能使用這臺(tái)切割機(jī)切割 K 次。Tim 當(dāng)然希望這個(gè)剩下來(lái)的多邊形面積最大，但是他該如何去切呢？寫一個(gè)程序：從文件中讀入鏡子以及 K 個(gè)位置的描述；計(jì)算出最優(yōu)切割方案；向輸出文件打印結(jié)果。輸入格式輸入文件的第一行包含一個(gè)實(shí)數(shù) R，表示圓形鏡子的半徑：1R100。兩個(gè)正整數(shù)：N 和 K：3KN200。以下 N 行，每行兩個(gè)數(shù)字，代表一個(gè)位置的坐標(biāo)，這個(gè)坐標(biāo)一定在以(0, 0)為圓