AOJ 1032 : Course Planning for Lazy Students
問題リンク:Course Planning for Lazy Students | Aizu Online Judge
問題概要:
n個の科目から最低取得単位数Uをこえる最小の科目数をもとめよ
使用した言語:C++
解説:
dfsだとTLEになったのでbitをもたせてbfsをした
mincost[1<
#include<cstdio> #include<iostream> #include<bitset> #include<deque> #include<algorithm> using namespace std; struct Pox { int state,cost; Pox(int state,int cost):state(state),cost(cost){} }; int main() { while(1) { int n,U,k,r; scanf("%d %d",&n,&U); if(n+U == 0) break; int mincost[1<<n]; for(int i=0;i<(1<<n);i++) mincost[i] = (1<<n); deque<Pox> deq; int G[n]; int c[n]; for(int i = 0;i<n;i++) { scanf("%d %d",&c[i],&k); G[i] = 0; for(int j=0;j<k;j++) { scanf("%d",&r); G[i] |= (1<<r); } } deq.push_back(Pox(0,0)); mincost[0] = 0; int ans = (1<<n); while(!deq.empty()) { Pox pox = deq.front(); deq.pop_front(); int num = __builtin_popcount(pox.state); if(num >= ans) continue; if(pox.cost >= U) { ans = min(ans,num); continue; } for(int i=0;i<n;i++) { if((pox.state >> i) & 1) continue; int pre = G[i]; pre &= pox.state; if(pre != G[i])//先修科目をすべてとっているか? continue; if(mincost[pox.state|(1<<i)] <= num+1) continue; mincost[pox.state|(1<<i)] = num+1; if(pox.cost + c[i] < U) deq.push_back(Pox(pox.state|(1<<i),pox.cost+c[i])); else ans = min(ans,num+1); } } cout << ans << endl; } return 0; }