生活随笔
收集整理的這篇文章主要介紹了
今年暑假不AC
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目1434：今年暑假不AC
時間限制：1 秒
內存限制：128 兆
特殊判題：否
提交：307
解決：180
題目描述： “今年暑假不AC？”“是的。”“那你干什么呢？”“看世界杯呀，笨蛋！”“@#$%^&*%...”確實如此，世界杯來了，球迷的節日也來了，估計很多ACMer也會拋開電腦，奔向電視作為球迷，一定想看盡量多的完整的比賽，當然，作為新時代的好青年，你一定還會看一些其它的節目，比如新聞聯播（永遠不要忘記關心國家大事）、非常6+7、超級女生，以及王小丫的《開心辭典》等等，假設你已經知道了所有你喜歡看的電視節目的轉播時間表，你會合理安排嗎？（目標是能看盡量多的完整節目）
輸入： 輸入數據包含多個測試實例，每個測試實例的第一行只有一個整數n(n<=100)，表示你喜歡看的節目的總數，然后是n行數據，每行包括兩個數據Ti_s,Ti_e (1<=i<=n)，分別表示第i個節目的開始和結束時間，為了簡化問題，每個時間都用一個正整數表示。n=0表示輸入結束，不做處理。
輸出： 對于每個測試實例，輸出能完整看到的電視節目的個數，每個測試實例的輸出占一行。
樣例輸入： 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
跟項目規劃一樣，對結束時間進行排序，然后對每個節目動態規劃式： dp[i]=max(dp[i-1],dp[k]+1) 0=<k<i,
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
struct PRO{int begt;int endt;
public:PRO(int begt_,int endt_):begt(begt_),endt(endt_){};};
std::vector<PRO> ps;
int maxP[101];
int findpm(int b,int e,int t){int id = b-1;//Attentionint mid;while(b<=e){ //ATTENTION? <=mid = (b+e)>>1;if(ps[mid].endt<=t){id = mid;b = mid+1;}else{e = mid-1;}}return id;
}bool lessThan(const PRO& pl,const PRO& pr){return pl.endt<pr.endt;
}
void init(int n){ps.clear();for(int i =0;i<=n;i++)maxP[i]=0;int bt;int et;ps.push_back(PRO(0,0)); //ATTENTIONfor(int i = 0;i<n;i++){scanf("%d %d",&bt,&et);ps.push_back(PRO(bt,et));}}
void getMax(int n){std::sort(ps.begin(),ps.end(),lessThan);for(int i = 1;i<n+1;i++){if(ps[i].begt>=ps[i-1].endt){maxP[i] = maxP[i-1]+1;continue;}int preid = findpm(0,i-1,ps[i].begt);maxP[i] = std::max(maxP[i-1],maxP[preid]+1);}printf("%d\n",maxP[n]);
}void judo(){int n;while(scanf("%d",&n)!=EOF && n){init(n);getMax(n);}
}
int main() {judo();//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!return 0;
}/**************************************************************Problem: 1434User: KESLanguage: C++Result: AcceptedTime:10 msMemory:1524 kb
****************************************************************/
總結
以上是生活随笔為你收集整理的今年暑假不AC的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
