a4_interval.cpp

该算法设计短小精悍

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define MAXN 50002
struct interval{
	int a,b,c;
}list[MAXN];
int s[MAXN],len[MAXN];
vector<int> from[MAXN];
int main() {
	int n,i,j,k,max,min;
	bool sign;
	while(scanf("%d",&n)!=EOF) {
		max=-1,min=MAXN+2;
		memset(s,0,sizeof s);
		for (i=0;i<n;i++) {
			scanf("%d%d%d",&list[i].a,&list[i].b,&list[i].c);
			list[i].a++,list[i].b++;
			from[list[i].b].push_back(i);
			if (list[i].a<min) min=list[i].a;
			if (list[i].b>max) max=list[i].b;
		}
		for (i=min;i<=max;i++) len[i]=from[i].size();
		do{
			sign=false;
			for (i=min;i<=max;i++) {
				if (s[i-1]>s[i]) {
					s[i]=s[i-1];
					sign=true;
				}
				for (j=0;j<len[i];j++) {
					k=from[i][j];
					if (s[list[k].a-1]+list[k].c>s[i]) {
						s[i]=s[list[k].a-1]+list[k].c;
						sign=true;
					}
				}
			}
			if (!sign) break;
			for (i=max-1;i>=min;i--) {
				if (s[i+1]-1>s[i]) {
					s[i]=s[i+1]-1;
					sign=true;
				}
			}
		}while(sign);
		for (i=min;i<=max;i++) 
			if (len[i]) from[i].clear();
		printf("%d\n",s[max]);
	}
	return 0;
}