AOJ 0579 - Hot days
動的計画法.数をこなしたいなあ.
std::absはC++11かららしい.
ごっちゃになってました.ご報告ありがとうございます.
#include<iostream> int main(){ //Cs[i][0]: min, Cs[i][1]: max, Cs[i][2]: 派手さ //dp[i][j]: i日目に服jを着た時の派手さの最大値 int D, N, Ts[200], Cs[200][3], dp[200][200]; const int INF = 1 << 24; std::cin >> D >> N; for(int i=0;i<D;i++){ std::cin >> Ts[i]; } for(int j=0;j<N;j++){ std::cin >> Cs[j][0] >> Cs[j][1] >> Cs[j][2]; } for(int i=0;i<200;i++){ for(int j=0;j<200;j++){ dp[i][j] = 0; } } int res = 0; for(int i=1;i<D;i++){ for(int j=0;j<N;j++){ if(Cs[j][0] <= Ts[i] && Ts[i] <= Cs[j][1]); else continue; for(int k=0;k<N;k++){ if(Cs[k][0] <= Ts[i-1] && Ts[i-1] <= Cs[k][1]); else continue; dp[i][j] = std::max(dp[i][j], std::abs(Cs[j][2]-Cs[k][2]) + dp[i-1][k]); res = std::max(res, dp[i][j]); } } } std::cout << res << std::endl; }