寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #M - ストラップ

JOI春合宿2014 オンラインジャッジから、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#M - ストラップ

www.ioi-jp.org

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#M - ストラップ
https://www.ioi-jp.org/camp/2014/2014-sp-tasks/index.html
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
const int num=2010;
int n,a[num],b[num],dp[num][2*num+1];
int main(void){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
  }
  for(int i=0;i<=2*num;i++){
    dp[0][i]=-2100000000;
  }
  dp[0][num+1]=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<=2*num;j++){
      dp[i+1][j]=-2100000000;
    }
    for(int j=0;j<=2*num;j++){
      int k=j+a[i]-1;
      if(k<0){
        continue;
      }
      if(k>2*num){
        k=2*num;
      }
      dp[i+1][k]=max(dp[i+1][k],dp[i][j]+b[i]);
      dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
    }
  }
  int ans=0;
  for(int i=num;i<=2*num;i++){
    ans=max(ans,dp[n][i]);
  }
  cout<<ans<<endl;
  return 0;
}