think: 1今晚終于AC道題目了…..這道題目感覺和貪心里面的區(qū)間區(qū)間覆蓋問題類似，只不過感覺這道題目明顯需要優(yōu)化子問題，因為有可能出現(xiàn)像【0， 7】，【1， 3】， 【3， 6】這樣的區(qū)間，不能因為先出現(xiàn)一個條件判斷了，之前自己做的區(qū)間覆蓋問題好像沒有想的這么深，看來之前自己區(qū)間覆蓋問題的AC有點水…，不過現(xiàn)在想明白了也很幸運(yùn) 2回歸題目，題目可以建立兩個結(jié)構(gòu)體數(shù)組，存儲各個節(jié)目開始的時間和結(jié)束的時間，然后用快排函數(shù)將輸入的按照開始時間升序排序，同一開始時間則按照結(jié)束時間升序排序，然后將最優(yōu)子問題存儲在另一個結(jié)構(gòu)數(shù)組中，需要注意的是第一個存儲和最后一個存儲，我用存儲的結(jié)構(gòu)數(shù)組是從下標(biāo)為1開始存儲的，這樣可以減少第一個存儲的判斷條件，融合了動態(tài)規(guī)劃思想的最優(yōu)子問題將貪心進(jìn)行優(yōu)化

sdut題目鏈接 hdoj原題鏈接

今年暑假不AC Time Limit: 1000MS Memory Limit: 65535KB

PRoblem Description “今年暑假不AC？” “是的。” “那你干什么呢？” “看世界杯呀，笨蛋！” “@#$%^&*%…” 確實如此，世界杯來了，球迷的節(jié)日也來了，估計很多ACMer也會拋開電腦，奔向電視了。 作為球迷，一定想看盡量多的完整的比賽，當(dāng)然，作為新時代的好青年，你一定還會看一些其它的節(jié)目，比如新聞聯(lián)播（永遠(yuǎn)不要忘記關(guān)心國家大事）、非常6+7、超級女生，以及王小丫的《開心辭典》等等，假設(shè)你已經(jīng)知道了所有你喜歡看的電視節(jié)目的轉(zhuǎn)播時間表，你會合理安排嗎？（目標(biāo)是能看盡量多的完整節(jié)目）

Input 輸入數(shù)據(jù)包含多個測試實例，每個測試實例的第一行只有一個整數(shù)n(n<=100)，表示你喜歡看的節(jié)目的總數(shù)，然后是n行數(shù)據(jù)，每行包括兩個數(shù)據(jù)Ti_s,Ti_e (1<=i<=n)，分別表示第i個節(jié)目的開始和結(jié)束時間，為了簡化問題，每個時間都用一個正整數(shù)表示。n=0表示輸入結(jié)束，不做處理。

Output 對于每個測試實例，輸出能完整看到的電視節(jié)目的個數(shù)，每個測試實例的輸出占一行。

Example Input 12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0

Example Output 5

Hint hdoj2037

Author hdojACM程序設(shè)計期末考試

以下為accepted代碼