POJ(PKU) 3616 Milking Time

N年ぶりにDPの問題を解いたけどなんとかできた。。。

解法：DP
dp[i] = max(dp[i-1],終わる時間がiの中で最も大きいもの);

実際問題から計算量O(N)しかありえないっぽいし解法しぼれたのでよかった。

#include <cstdio>
#include <algorithm>

using namespace std;

typedef pair<int,int> P;
typedef pair<int,P> PP;
int dp[1000003] = {0};
int main(){
  
  int n,m,r;

  
  PP l[1002];
  
  scanf("%d%d%d",&n,&m,&r);
  
  for(int i = 0;i < m;i++){
    scanf("%d%d%d",&l[i].second.first,&l[i].first,&l[i].second.second);
  }
  
  sort(l, l + m);
  
  int nau = 0;

  for(int i = 1;i <= n;i++){
    int m = 0;
    while(1){
      if(l[nau].first == i){
	int sa = l[nau].second.first - r;
	if(sa > 0){
	  m = max(m,dp[sa]+l[nau].second.second);
	}else{
	  m = max(m,l[nau].second.second);
	}
      }else{
	break;
      }
      nau++;
    }
    dp[i] = max(dp[i-1],m);
  }

  printf("%d\n",dp[n]);
  
  return 0;
  
}