PythonでJOI難易度6を埋める #12

C - 夜店 (Night Market)

問題からDP感がでてる．時刻からまでのDP1，時刻からまでのDP1で解く．
DP1[ i ][ j ] := お店 i まで調べて，時刻jまでに実現できる最大の楽しさの和．
DP2は1と考えかたが逆で，
DP2[ i ][ j ] := 時刻 j からお店 i ~ N を訪ずれたときの最大の楽しさの和．

どちらのDPをお店に入るか，入らないかの2択のうち大きい方で更新していきます． 参考にした記事にも書いてあるように，Pythonだと間に合わないので C++ をコピペしました，許して

//#define _GLIBCXX_DEBUG

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define uint unsigned int
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1000000000;

int main() {
    IOS;
    int N,T,S;
    cin >> N >> T >> S;
    vector<int>A(N);
    vector<int>B(N);

    for (int i=0; i<N; i++){
        cin >> A[i] >> B[i];
    }

    vector<vector<int>>dp(N+1, vector<int>(T+1));
    // dp[a][b] := 店aまで見て時刻bまでに実現できる最大の楽しさ

    for (int i=0; i<N; i++){
        for (int j=0; j<=S; j++){
            chmax(dp[i+1][j], dp[i][j]);
            if (j-B[i] >= 0)chmax(dp[i+1][j], dp[i][j-B[i]] + A[i]);
        }
    }
  vector<vector<int>>dp2 (N+1, vector<int>(T+1));
  for (int i=N; i>=1;i--){
    for (int j=T; j>=S; j--){
      chmax(dp2[i-1][j], dp2[i][j]);
      if (j+B[i-1]<=T) chmax(dp2[i-1][j], dp2[i][j+B[i-1]]+A[i-1]);
    }

  }
    int ans = -INF;
    for (int i=0; i<N; i++) chmax(ans, dp[i][S]+dp2[i+1][S]);
    cout << ans << endl;
}

できたこと

• 二つのDPに分けて考える

学んだこと

• C++ での，逆順でのfor文
• 2つのDPを用いたときの，繋げ方