其實這題是可以作到O(N^2)的。
要先有一個概念:如果最後有合奏的學姐序列依照合奏時間用S1~Sk表示。
那麼對任意i,一定有Si的編號 < S(i+1)的編號。
也就是不會有a區間比b區間前面 但是a學姐比b學姐晚合奏完的情況。
怎麼證明呢?假設最佳序列是S'1~S'k而且其中存在一個i,S'i的編號 > S'(i+1)的編號
但經過一點點的小證明可以發現,把這兩個學姐交換順序也一定存在一個合法的合奏方案。
//因為區間有非嚴格遞增性才會合理。
所以我們可以用DP[j]表示做完前i個學姐,取了j個學姐時最右界的位置。
每個轉移O(1),總複雜度O(N^2)
#include <cstdio>
#define INF 1000100
int dp[1010], N, D, R, P, dm;
inline int fmax(int a, int b) {return a>b?a:b;}
int main() {
while(~scanf("%d", &N) && N) {
for(int i=1; i<=N; i++) dp[i] = INF;
for(int i=0; i<N; i++) {
scanf("%d%d%d", &D, &R, &P);
for(int j=i; j>=0; j--) {
dm = fmax(D, dp[j]+1);
if(dm+P-1 <= R && dp[j+1] > dm+P-1)
dp[j+1] = dm+P-1;
}
}
for(int i=N; i>=0; i--)
if(dp[i] != INF) {
printf("%d\n", i);
break;
}
}
}