問題
http://topcoder.bgcoder.com/print.php?id=927
テレビの番組表があり、各番組ごとに開始時間と終了時間が与えられる。
できるだけ多くのテレビ番組をみたいが、放送時間が重複しているときは同時にみることができない。
このとき、できるだけ多くのテレビ番組をみたときのテレビの視聴時間を求める。
解き方
開始時間と終了時間は２４時間単位でループしているので、単純に終了時間のみをみるだけでは正確な答えが求まらない。
そこでｄｐを用いて、一番最初に見たプログラムと一番最後に見たプログラムを状態数に持つ。まだみていないプログラムについて、最後にみたプログラムの終了時間以降にはじまり、ループして最初にみたプログラムよりも前の時間に終わることができるものについて全ての場合を調べる。
メモ化しても５０＊５０なので計算量とメモリ量も足りる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[51][51],from[51],to[51],n;
vector<pair<int,int> > p;
class TVWatching {
public:
int calc(string str){
int ret=(str[0]-'0')*600+(str[1]-'0')*60+(str[3]-'0')*10+(str[4]-'0');
if(ret>=720)ret-=720;
return str.substr(5,2)=="PM" ? ret+720 : ret;
}
int dfs(int l,int r){
if(dp[l][r]!=-1)return dp[l][r];
int ret=0;
FORE(i,0,n)if(from[i]>=to[r] && to[i]<=from[l]+1440){
ret=max(ret,to[i]-from[i]+dfs(l,i));
}
return dp[l][r]=ret;
}
int mostMinutes(vector<string> programs) {
n=programs.size();
memset(from,0,sizeof(from));
memset(to,0,sizeof(to));
memset(dp,-1,sizeof(dp));
FORE(i,0,n){
stringstream out(programs[i]);
string str1,str2,tmp;
out>>str1>>tmp>>str2;
int start=calc(str1),end=calc(str2);
if(start>=end)end+=1440;
from[i]=start,to[i]=end;
}
int ret=0;
FORE(i,0,n)ret=max(ret,to[i]-from[i]+dfs(i,i));
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[51][51],from[51],to[51],n;
vector<pair<int,int> > p;
class TVWatching {
public:
int calc(string str){
int ret=(str[0]-'0')*600+(str[1]-'0')*60+(str[3]-'0')*10+(str[4]-'0');
if(ret>=720)ret-=720;
return str.substr(5,2)=="PM" ? ret+720 : ret;
}
int dfs(int l,int r){
if(dp[l][r]!=-1)return dp[l][r];
int ret=0;
FORE(i,0,n)if(from[i]>=to[r] && to[i]<=from[l]+1440){
ret=max(ret,to[i]-from[i]+dfs(l,i));
}
return dp[l][r]=ret;
}
int mostMinutes(vector<string> programs) {
n=programs.size();
memset(from,0,sizeof(from));
memset(to,0,sizeof(to));
memset(dp,-1,sizeof(dp));
FORE(i,0,n){
stringstream out(programs[i]);
string str1,str2,tmp;
out>>str1>>tmp>>str2;
int start=calc(str1),end=calc(str2);
if(start>=end)end+=1440;
from[i]=start,to[i]=end;
}
int ret=0;
FORE(i,0,n)ret=max(ret,to[i]-from[i]+dfs(i,i));
return ret;
}
};