SRM602 Div1 Easy TypoCoderDiv1

問題概要

レート2200以上と未満で色が変わるシステムで初期レートxと各コンテストのレート増減値D_iが与えられる.
一度レート2200以上になると次は2200未満にならなければいけないという条件のもと何回色を変えられるか.

解法

解説AC.
終わったコンテストの回数と現在のレートを持ってDP.
各状態からレート上昇と下降に遷移するが,上昇したとき2200以上になる場合は次に下降したところに遷移.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(ll i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(ll i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
class TypoCoderDiv1{
public:
    int getmax(vi d,int x){
        int n=d.size();
        vvi dp(n+1,vi(2200,-1));
        dp[0][x]=0;
        int res=0;
        REP(i,n){
            REP(j,2200){
                if(dp[i][j]==-1){
                    continue;
                }
                if(i+1<n){
                    if(j+d[i]>=2200&&j+d[i]-d[i+1]<2200){
                        chmax(i+2<n?dp[i+2][max(0LL,j+d[i]-d[i+1])]:res,dp[i][j]+2);
                    }else if(j+d[i]<2200){
                        chmax(dp[i+1][j+d[i]],dp[i][j]);
                    }
                }else{
                    if(j+d[i]>=2200){
                        chmax(res,dp[i][j]+1);
                    }
                    chmax(res,dp[i][j]);
                }
                chmax(dp[i+1][max(0LL,j-d[i])],dp[i][j]);
            }
        }
        return res;
    }
};