5535 - 패셔니스타

https://www.acmicpc.net/problem/5535

각 날짜에 대해 최고기온을 고려해서 입을 수 있는 옷들을 정리한다.

각 날짜마다 한 옷을 선택한다고 하면, D일동안 N개의 옷으로는 경우의 수는 \(O(N^D)\) 이다.

dp 점화식을

dp[D][N] = D번째 날에 N번째 옷을 선택했을 때의 문제의 정답

이라고 하면 \(O(ND)\) 으로 줄일 수 있다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef long long lld;

int D, N;
vector<int> a[201];

int dp[201][201];

int f(int pos, int sel){
     if(pos == D-1) return 0;
     
     int& r = dp[pos][sel];
     if(r != -1) return r;
     
     r = 0;
     for(int i=0; i < a[pos+1].size(); ++i){
      int diff = abs(a[pos][sel] - a[pos+1][i]);
      r = max(r, diff + f(pos+1, i));
     }
     return r;
}

int main(){
     memset(dp, -1, sizeof(dp));
     
     scanf("%d %d", &D, &N);
     int T[D];
     for(int i=0; i<D; ++i) scanf("%d", &T[i]);
     for(int i=0; i<N; ++i){
      int low, high, c;
      scanf("%d %d %d", &low, &high, &c);
      for(int j=0; j<D; ++j){
       if(low <= T[j] && T[j] <= high){
        a[j].push_back(c);
       }
      }
     }
     
     int r = 0;
     for(int i=0; i < a[0].size(); ++i){
      r = max(r, f(0, i));
     }
     printf("%d", r);
     
     
     return 0;
}