Google code jam 2017 Round1C B. Parenting Partnering (DP編)

2017-05-01

16:42 |

(あとで)
DPでも解けるということでやってみた。なるほど簡潔だ。

// dp[i][j][k][l]
// = 最初の割当が i (0:A 1:B), j+1分終わった時点, A の割当時間が k 分, 最後の割当が l (0:A 1:B) な状態での, 日をまたぐ切り替えを考慮しない最小切り替え回数
int dp[2][1440][721][2];

int INF = 1<<30;

int main() {
	int test_cases;
	cin>>test_cases;
	ll A,B, s, e;
	REP(ttt, test_cases) {
		cin>>A>>B;
		VI tl(1440, -1); // 0: A 1: B -1: none
		REP(i, A) {
			cin>>s>>e;
			RANGE(i, s, e) tl[i] = 0;
		}
		REP(i, B) {
			cin>>s>>e;
			RANGE(i, s, e) tl[i] = 1;
		}
		REP(bi, 2) REP(mi, 1440) REP(ai, 721) REP(ei, 2) dp[bi][mi][ai][ei] = INF;
		REP(bi, 2) REP(ei, 2) dp[bi][0][ei==0][ei] = bi!=ei;
		REP(bi, 2) REP(mi, 1440) REP(ai, 721) REP(ei, 2) REP(nei, 2) {
			int old = dp[bi][mi][ai][ei];
			int nbi = bi;
			int nmi = mi+1;
			int nai = ai + (nei==0);
			int cost = ei!=nei;
			if(nmi<1440 && tl[nmi]!=nei && nai<=720) {
				dp[nbi][nmi][nai][nei] = min(dp[nbi][nmi][nai][nei], old + cost);
			}
		}
		int ans = INF;
		REP(bi, 2) REP(ei, 2) {
			// 日をまたぐ切り替えの考慮
			int lans = dp[bi][1439][720][ei]+(bi!=ei);
			ans = min(ans, lans);
		}

		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}