読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 2366 : Elevator

AOJ 動的計画法 ビットDP

問題概要:Elevator | Aizu Online Judge

問題概要:
日本語なので略

解法:
動的計画法を行う
荷物があるフロアの中で最も上にあるフロアから1フロアずつ全ての荷物をもっていきながらおりていく
そのフロアにある荷物を全て1つ下のフロアに持っていくための最小移動回数をbitDPで求める
dp[(1<<(そのフロアにある荷物の数))] := 最小の移動回数 とする
今のフロアの状態をループで全て試し、そのなかで下の階に移動させる荷物もビットで全ての状態を試す
もし最初に荷物があるフロアの中で最も上にあるフロアにいない場合はそこまでの移動コストを答えに加える

コード:

struct P
{
  int weight,index;
  P(int weight=inf,int index=inf):weight(weight),index(index){}
  bool operator < (const P& a)const
  {
    return weight < a.weight;
  }
};

int n,m,W;

int main()
{
  int k;
  scanf("%d %d %d",&n,&m,&W);
  
  int idx = 0;
  vector<vector<P> > vec;
  vector<int> FLOOR;

  rep(i,n)
    {
      scanf("%d",&k);
      if(k == 0)
	{
	  if(i == 0)
	    {
	      FLOOR.push_back(i);
	      vec.push_back(vector<P>());
	    }
	  continue;
	}
      int cur = vec.size();
      vec.push_back(vector<P>(k));
      FLOOR.push_back(i);
      rep(j,k)
	{
	  scanf("%d",&vec[cur][j].weight);
	}
    }

  if(FLOOR[FLOOR.size()-1] == 0)
    {
      puts("0");
      return 0;
    }

  int ans = FLOOR[FLOOR.size()-1]+1-m;
  for(int i=FLOOR.size()-1;i>=1;i--)
    {
      //cout << "cost = " << FLOOR[i] << " - " << FLOOR[i-1] << endl;
      int cost = FLOOR[i] - FLOOR[i-1];
      assert(cost >= 0);
      int SIZE = vec[i].size();
      //cout << "SIZE = " << SIZE << endl;
      int dp[(1<<SIZE)];
      rep(j,(1<<SIZE))dp[j] = inf;
      dp[0] = 0;
      rep(state,(1<<SIZE))//今のフロアの状況 0 -> まだ移動してない, 1 -> 移動したたそ〜
	{
	  if(dp[state] == inf)continue;
	  vector<P> tmp;//まだこのフロアにあるものたそ〜
	  rep(j,SIZE)
	    {
	      if((state>>j) & 1)continue;
	      tmp.push_back(P(vec[i][j].weight,j));
	    }

	  int limit = tmp.size();
	  rep(j,(1<<limit))//次に移動するもの
	    {
	      int sum = 0;
	      int tstate = 0;
	      rep(k,limit)
		{
		  if((j>>k) & 1)
		    {
		      tstate |= (1<<tmp[k].index);
		      sum += tmp[k].weight;
		    }
		}
	      assert(sum >= 0);
	      if(sum > W)continue;
	      assert((state ^ tstate) == (state | tstate));
	      int nstate = state | tstate;
	      dp[nstate] = min(dp[nstate],
			       dp[state]+2);
	    }
	}
      rep(j,vec[i].size())vec[i-1].push_back(vec[i][j]);
      assert((dp[(1<<SIZE)-1]-1)*cost >= 0);
      ans += (dp[(1<<SIZE)-1]-1)*cost;//新たな値を得るたそ〜
      assert(ans >= 0);
      //cout << "ans = " << ans << " dp = " << dp[(1<<SIZE)-1] << endl;
    }

  printf("%d\n",ans);//えるたそ〜

  return 0;
}