AOJ2321 Butterfly

問題リンク Butterfly

• 概要

後回し

• 解法

時間が[6〜22]の17通りしかないのでビットを立てることで2^17までの整数で時間帯を表現することができます。
デートに使う時間は[S, E)という半開区間であることに注意してビットを立てます。
各男性のデートに使う時間をd[i]、満足度をs[i]とし、DPで解きます。
dp[S]: 女性がデートに使える時間帯がSのときの最大満足度
という表を作ります。このとき、男性 i と時間の都合が合う条件は Sが完全にd[i]を含んでいるときなので
S & d[i] = d[i]
と書けます。女性が使える残りの時間はS - d[i]となります。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Butterfly
public class AOJ2321 {

	int n;
	int[] d, s, dp;
	
	int get(int S){
		if(dp[S]!=-1)return dp[S];
		int max = 0;
		for(int i=0;i<n;i++){
			if((S&d[i])==d[i]){
				max = Math.max(max, s[i]+get(S-d[i]));
			}
		}
		return dp[S] = max;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt();
			if(n==0)break;
			d = new int[n]; s = new int[n];
			for(int i=0;i<n;i++){
				int k = sc.nextInt();
				s[i] = sc.nextInt();
				while(k--!=0){
					int S = sc.nextInt()-6, E = sc.nextInt()-6;
					for(int j=S;j<E;j++)d[i]+=1<<j;
				}
			}
			dp = new int[1<<16];
			Arrays.fill(dp, -1);
			System.out.println(get((1<<16)-1));
		}
	}
	
	public static void main(String[] args) {
		new AOJ2321().run();
	}
}