sparseなDP

定数倍高速化！（素振り）

手抜き

using T = tuple<int, int, int>;
map<T, int> dp;

auto push=[&](int a,int b,int c,int d){
  if(!dp.count(T(a,b,c))) dp[T(a,b,c)]=INF;
  chmin(dp[T(a,b,c)],d);
};

ちょっと改善

auto T = [&](int a, int b, int c){return (a*MAX_B+b)*MAX_C+c;};
unordered_map<int, int> dp;

auto push=[&](int a,int b,int c,int d){
  if(!dp.count(T(a,b,c))) dp[T(a,b,c)]=INF;
  chmin(dp[T(a,b,c)],d);
};

気合

auto T = [&](int a, int b, int c){return (a*MAX_B+b)*MAX_C+c;};
vector<int> dp(T(MAX_A,MAX_B,MAX_C),-1);

vector<int> used;
auto push=[&](int a,int b,int c,int d){
  if(dp[T(a,b,c)]<0){
    dp[T(a,b,c)]=INF;
    used.emplace_back(T(a,b,c));
  }
  chmin(dp[T(a,b,c)],d);
};

for(int v:used) dp[v]=-1;

問題例

leetcode.com

おわりに

5ペナじゃあないんだよ