POJ 2184 Cow Exhibition

問題文

DP強化週間。

整数の数列SとFが与えられる。S+Fの部分和の最大値を計算する。しかしそのときのSの部分和、Fの部分和ともに0以上でなくてはならない。という問題。

dp[i+1][j]:=(数列のi番目まででSの部分和がjである時のFの部分和の最大値)でDP。メモリが足りないので使い回しする。配列のインデクスが負にならないように予めゲタを履かせておく必要がある。

考え方がわからず、いろんなサイトを見てしまった。まだこれくらいのはできないんだな。でもとても良い問題だと思う。

以下ソース。

const int M = 200002;

int dp[2][M];
int S[101], F[101];

int main(int argc, char **argv){
  int N; cin >> N;
  for(int i = 0; i < N; i++) cin >> S[i] >> F[i];
  for(int i = 0; i < 2; i++)
    for(int j = 0; j < M; j++)
      dp[i][j] = -INF;

  dp[0][100000] = 0;
  int *cur = dp[0], *next = dp[1];
  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
      if(cur[j] != -INF){
	//Don't use S[i]
	next[j] = max(next[j], cur[j]);
	//Use S[i]
	next[j + S[i]] = max(next[j + S[i]], cur[j] + F[i]);
      }
    }
    swap(cur, next);
  }
  
  int ans = -INF;

  // cur[i] is a partial sum of F when a partial sum of S is i - 100000
  for(int i = 100000; i < M; i++)
    if(cur[i] >= 0)
      ans = max(ans, i - 100000 + cur[i]);

  cout << ans << endl;
  return 0;
}

S,Fの部分和が0以上という条件に引きずられてこむずかしく考えていた。負のものも含めてとりあえず全部求めてみて0以上のものをつまみ出して、Fも0以上ならいいや、というとこが思いつかなかった。こういう問題は多いだろうと思う。

忙しくなくなったので、これから少しずつペースを上げていく。