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

解いた問題のソースコードと解説など。


POJ 3211 Washing Clothes

問題文
DP強化週間。

色付きの衣類の、それを洗う時間とその色が入力として与えられる。洗う人が二人いて、同じ色の衣服は二人が同じ時間(区間)にいっぺんに全て洗う必要がある。つまり、片方が洗い終わってももう片方が終わるのを待つ必要がある。また同一の衣類を二人で同時に洗うことはできない。全ての衣類を洗うのにかかる最短の時間を求めよ、という問題。

各色の衣類は完全に時間帯を分けて洗う必要があるので、ある色の衣類を二人で洗う最短時間を各々の色について計算して足し上げればいい。
各色に入力を分けたとして、ある色の衣類を全て洗うのにtotal秒かかるとする。二人で洗うのでもっとも効率のいい洗い方は(可能なら)total / 2秒でできる。ここまでくればあとは(同色の衣類の中から)いくつかの衣類を選んでその和をなるべくtotal / 2秒に近づけるだけなので部分和のDPの問題(12761742)に置き直せる。二人はどちらか長くかかる方を待たねばならないのでかかる時間は(total + 1) / 2秒以降で初めて部分和で構成できる秒数になる。
dp[i]:=(i秒である色の衣類を洗おうとするときに余る衣類の数)

int dp[100001];

int main(int argc, char **argv){
  int M, N;
  while(cin >> M >> N){
    if(N == 0 && M == 0) break;

    //Input
    map<string, vector<int> > shirt;
    string color;
    int time;
    for(int i = 0; i < M; i++) cin >> color;
    for(int i = 0; i < N; i++){
      cin >> time >> color;
      shirt[color].push_back(time);
    }

    int ans = 0;

    //Wash same color clothes
    for(map<string, vector<int> >::iterator it = shirt.begin();
	  it != shirt.end(); it++){

      vector<int> tmp = it -> second;

      //DP
      sort(tmp.begin(), tmp.end());
      int total = accumulate(tmp.begin(), tmp.end(), 0);
      memset(dp, -1, sizeof(dp));
      dp[0] = 0;
      for(int i = 0; i < (int)tmp.size(); i++){
	for(int j = 0; j <= total; j++){
	  if(dp[j] >= 0)
	    dp[j] = 1;
	  else if(j < tmp[i] || dp[j - tmp[i]] <= 0)
	    dp[j] = -1;
	  else
	    dp[j] = dp[j - tmp[i]] - 1;
	}
      }

      //Shortest time to wash same color clothes by two people
      int i;
      for(i = (total + 1) / 2; i <= total; i++)
	if(dp[i] >= 0)
	  break;
    
      ans += i;
    }
    
    cout << ans << endl;
  }
  return 0;
}

このブログ始めて、初めて自力で解けた。一発AC。
でもソートいらなかったかも。。

しょげないでよBaby 眠れば治る