第１２回日本情報オリンピック 予選（オンライン ）D－暑い日々（Hot days）

問題

atcoder.jp

JOIの難易度５の問題です。

考察

ぱっと見でDPか貪欲かという感じですが日数と服の種類の制約がそれぞれ２００なのでDPで書いてみました。

i日目に服jを選んだときのスコアの最大値をdp[i][j]とおいてみました。

i日目とi+1日目に選べる服かどうかを判定し更新していきます。

書いてみた

とりあえずしゃらしゃらっと書いてみました。
CEはでなかったもののWA。
もう少し考えてみます。

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

int main(){
  int D,N;
  cin>>D>>N;
  
  int dp[210][210]={};
  
  //気温入力
  int T[210];
  for(int i=0;i<N;i++){
    cin>>T[i];
  }
  
  //服入力
  int A[210],B[210],C[210];
  for(int j=0;j<N;j++){
    cin>>A[j]>>B[j]>>C[j];
  }
  for(int i=1;i<D;i++){
    for(int j=0;j<N;j++){   
      for(int k=0;k<N;k++){
        if(A[i-1]<=T[i-1] && B[i-1]>=T[i-1] && A[i]<=T[i] && B[i]>=T[i]){
          dp[i][k]=max(dp[i][k],dp[i-1][j]+abs(C[j]-C[k]));
        }
      }
    }
  }
  int maxans=0;
  for(int i=0;i<N;i++){
    maxans=max(maxans,dp[N-1][i]);
  }
  cout<<maxans<<endl; 
  return 0;
}

ACしたコード

coutデバッグをしまくって添え字の間違いを直しました。
どうしてこんなに間違いまくるのか我ながら呆れますが、これもトレーニングかな。

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

int main(){
  int D,N;
  cin>>D>>N;
  
  int dp[210][210]={};
  
  //気温入力
  int T[210];
  for(int i=0;i<D;i++){
    cin>>T[i];
  }
  
  //服入力
  int A[210],B[210],C[210];
  for(int j=0;j<N;j++){
    cin>>A[j]>>B[j]>>C[j];
  }
  for(int i=1;i<D;i++){
    for(int j=0;j<N;j++){   
      for(int k=0;k<N;k++){
        if(A[j]<=T[i-1] && B[j]>=T[i-1] && A[k]<=T[i] && B[k]>=T[i]){
          dp[i][k]=max(dp[i][k],dp[i-1][j]+abs(C[j]-C[k]));
          //cout<<dp[i][k]<<" "<<i<<" "<<k<<" "<<abs(C[j]-C[k])<<endl;
        }
      }
    }
  }
  int maxans=0;
  for(int i=0;i<N;i++){
    maxans=max(maxans,dp[D-1][i]);
  }

  for(int i=0;i<D;i++){
    for(int j=0;j<N;j++){
      //cout<<dp[i][j]<<" "<<i<<" "<<j<<endl;
    }
  }
   cout<<maxans<<endl;  
  return 0;
}