JOI春合宿2014 Day4-3 Straps

解法

みた感じDPだけど微妙に出来なみがあるDP。ちょっと考えて、
dp[i][j]: i番目のストラップまで見たときに、残り端子数がj個のときの嬉しさの最大値
と定義してあげると上手くいく。
jが負値になる(=端子がj個足りない)ことがあるので、配列外参照しないようにいい感じにやる。
初期状態がdp[0][N + 1] ← 0としてあるのは、そのため。N個くらい以上端子が足りなくなったら絶望だからそこら辺にずらしておく。

ソース

#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;

int dp[2][4001]; //ストラップ接続数の余裕
int N, A[2000], B[2000];
int main(){

  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A[i] >> B[i];
  }
  fill_n( *dp, 2 * 4001, -INF);
  dp[0][N + 1] = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j <= 2 * N; j++){
      if(dp[i&1][j] == -INF || j + A[i] - 1 < 0) continue;
      dp[(i + 1)&1][j] = max(dp[(i + 1)&1][j], dp[i&1][j]);
      dp[(i + 1)&1][min( 2 * N, j + A[i] - 1)] = max( dp[(i + 1)&1][min( 2 * N, j + A[i] - 1)], dp[i&1][j] + B[i]);
    }
  }
  cout << *max_element( dp[N & 1] + N, dp[N & 1] + 2 * N + 1) << endl;
}