yukicoder : No.733 分身並列コーディング

こっちの方が簡単だったな…。
https://yukicoder.me/problems/no/733

問題

N個の問題があり、それぞれt[i]の時間で解ける。
何人かでN個の問題を解くことを考える。
1つの問題は1人しか解くことができず、かつ各人同時に２問以上を解くことはできない。
全問解くのにかかる時間をT以下にするには何人必要か。

解法

Nの上限が17なので、O(3^N)解法であることが推測できる。
dp(mask) = maskに示すbitmaskに相当する問題を時間T以下で解ききる最少人数

maskに対応する問題のt[i]の総和がT以下ならdp(mask)=1である。
そうでない場合、smask⊂maskを総当たりしdp(mask)=min(dp(smask)+dp(smask^mask))を求めよう。
bitmaskの部分集合を求めるテクは他にも既出なので省略。

int T;
int N;
int A[17];
int dp[1<<17];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,1<<N) {
		dp[i]=101010;
		int tot=0;
		FOR(j,N) if(i&(1<<j)) tot+=A[j];
		if(tot<=T) dp[i]=1;
	}
	for(int mask=1;mask<1<<N;mask++) {
		for(int i=mask; i>0; i=(i-1)&mask) {
			dp[mask] = min(dp[mask],dp[i]+dp[i^mask]);
		}
	}
	cout<<dp[(1<<N)-1]<<endl;
	
}

まとめ

こっちは典型なので瞬殺だった。