2013
12-13

# 九度-1499-项目安排[解题代码]

st、ed、value取值均在32位有符号整数（int）的范围内，输入数据保证所有数据的value总和也在int范围内。

3
1 3 6
4 8 9
2 5 16
4
1 14 10
5 20 15
15 20 8
18 22 12

16
22


cpp 代码如下：
#include <stdio.h>
#include <algorithm>
using namespace std;
int n;
class P{
public:
int st,ed,value;
};
P p[10001];
int dp[10001]; //dp[i]安排前i个项目，多能到得到的最大value
bool cmp(const P & p1, const P & p2){
return p1.ed < p2.ed;
}

int main(){
int n, i, j;
while(scanf("%d", &n) != EOF){
for(i=1; i<=n; i++){
scanf("%d %d %d", &p[i].st, &p[i].ed, &p[i].value);
dp[i] = 0;
}
sort(p+1, p+n+1, cmp);
dp[0] = 0;
for(i=1; i<=n; i++){
for(j=i-1; j>0; j--){
if(p[i].st >= p[j].ed)
break;
}
dp[i] = dp[j] + p[i].value;
if(dp[i] < dp[i-1])
dp[i] = dp[i-1];
}
printf("%d\n",dp[n]);
}
return 0;
}

/**************************************************************
Problem: 1499
User: coder
Language: C++
Result: Accepted
Time:250 ms
Memory:1176 kb
****************************************************************/

1. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}