2063-TV Watching

問題概要

テレビではさまざまな番組を見ることが出来る．
番組はそれぞれ満足度という数値を持ち，満足度は生で見る時と，録画してみる時で異なる．
録画機械は同時に一つの番組までしか録画することは出来ず，またあなたはレテビで同時に一つの番組しか生で見ることも出来ない．生で見ている番組を録画しても満足度は上昇しない．
このとき，満足度の合計を最大化せよ．

解法

メモ化再帰．
人間側の現在の時間t1と録画機械の現在の時間t2を元に考える．
同じ番組を録画機械と人間の両方が見ることを防ぐために，
t1=t2の時はその見方を全探索する．
t1≠t2の時は小さい方を進める(番組を見るか見ずに次の時間に進む)．

実装(C++)

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define REP(i,x) for(int i=0;i<(int)x;i++)
int string2time(string t){
	return atoi(t.substr(0,2).c_str())*60+atoi(t.substr(3,2).c_str());
}
typedef pair<int,int> P;
int n;
P t[1000];
int score[1000][2];
string t1,t2,t3;
vector<int> prog[24*60];
int dp[24*60][24*60];
int solve(int t1,int t2){
	if(t1==24*60)return 0;
	if(dp[t1][t2]>=0)return dp[t1][t2];
	int &res=dp[t1][t2];
	res=0;
	if(t1==t2){
		res=solve(t1+1,t2+1);
		REP(i,prog[t1].size()){
			res=max(res,solve(t[prog[t1][i]].second,t2+1)+score[prog[t1][i]][0]);
		}
		REP(i,prog[t1].size()){
			res=max(res,solve(t1+1,t[prog[t1][i]].second)+score[prog[t1][i]][1]);
		}
		REP(i,prog[t1].size()){
			REP(j,prog[t1].size()){
				if(i==j)continue;
				res=max(res,solve(t[prog[t1][i]].second,t[prog[t1][j]].second)+score[prog[t1][i]][0]+score[prog[t1][j]][1]);
			}
		}
	}else if(t1>t2){
		//t2を進める
		res=solve(t1,t2+1);
		REP(i,prog[t2].size()){
			res=max(res,solve(t1,t[prog[t2][i]].second)+score[prog[t2][i]][1]);
		}
	}else{
		res=solve(t1+1,t2);
		REP(i,prog[t1].size()){
			res=max(res,solve(t[prog[t1][i]].second,t2)+score[prog[t1][i]][0]);
		}
	}
	return res;
}
int main() {
	for(;cin>>n,n;){
		for(int i=0;i<24*60;i++)prog[i].clear();
		memset(dp,-1,sizeof(dp));
		for(int i=0;i<n;i++){
			cin>>t1>>t2>>t3>>score[i][0]>>score[i][1];
			t[i].first=string2time(t2);
			t[i].second=string2time(t3);
			prog[t[i].first].push_back(i);
		}
		cout<<solve(0,0)<<endl;
	}
	return 0;
}