AOJ0579 暑い日々

joi-yosen

~DP~

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){

  int d,n;

  int kion[203] = {0};
  int huku[203][3] = {0};

  int dp[203][203] = {0};

  scanf("%d%d",&d,&n);

  for(int i = 0;i < d;i++){
    scanf("%d",&kion[i]);
  }

  for(int i = 0;i < n;i++){
    scanf("%d%d%d",&huku[i][0],&huku[i][1],&huku[i][2]);
  }


  for(int i = 2;i <= d;i++){
    for(int j = 0;j < n;j++){
      if(kion[i-1] <= huku[j][1] && kion[i-1] >= huku[j][0]){
	for(int k = 0;k < n;k++){
	  if(kion[i-2] <= huku[k][1] && kion[i-2] >= huku[k][0]){
	  dp[i][j] = max(dp[i][j],abs(huku[k][2] - huku[j][2])+dp[i-1][k]);
	  }
	}
      }
    }
  }
  int ans = 0;

  for(int i = 0;i < n;i++){
    ans = max(ans,dp[d][i]);
  }

  printf("%d\n",ans);

  return 0;

}