こっちの方が簡単だったな…。
https://yukicoder.me/problems/no/733
問題
N個の問題があり、それぞれt[i]の時間で解ける。
何人かでN個の問題を解くことを考える。
1つの問題は1人しか解くことができず、かつ各人同時に2問以上を解くことはできない。
全問解くのにかかる時間を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; }
まとめ
こっちは典型なので瞬殺だった。