xtu1148 dp

1209 단어 
#include <stdio.h>
#include <algorithm>
 
struct Node{
  int s,t,v;
 }test[100005];
 
using namespace std;
 
bool cmp(Node a,Node b){
  return a.t <= b.t;
 }
 
__int64 dp[100005];
 
int max(int a,int b){
  return a > b ? a : b;
 }
 
int find(int i,int n){
  int low = 0,max = n,m;
  while(1){
   if (max - low == 1) 
       return low;
   m = (low + max) / 2;
   if (test[i].s >= test[m].t)     
       low = m;
   else 
       max = m;
  }
//         test[i].s == test[m].t    m，            test[x].t  test[i].
//           s[i]    t[x],       ，    ！
 }
 
int main (){
  int n,i;
 
 while(scanf("%d",&n) != EOF){
   for(i = 0;i < n;i++){
    scanf("%d%d%d",&test[i].s,&test[i].t,&test[i].v);
    if (test[i].v <= 0){
     i--;
     n--;
    }
   }
   sort(test,test + n,cmp);
   memset(dp,0,sizeof(dp));
   dp[0] = test[0].v;
   for(i = 1;i < n;i++){
       if(test[i].s < test[0].t) dp[i] = test[i].v > dp[i-1] ? test[i].v : dp[i-1];
    else {
    int last = find(i,n);
    dp[i] = max(dp[i-1],dp[last] + test[i].v); 
    }
   } 
   printf("%lld
",dp[n-1]);
  }
  return 0;
 }

 
Mac에서 Docker를 사용하여 Linux 버전 Swift 테스트
기술서를 한 권 썼다

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage