s<=100, e<=100, s<=e
c<=10000
Output
對於每組數據，輸出吉哥可獲得的最高工資數。
Sample Input
1
10 5
1 5 100
3 10 10
5 10 100
1 4 2
6 12 266
Sample Output
102
剛開始想到的是貪心，後來覺得不行，就覺得應該是dp。dp[i]表示到第i天結束時能夠得到的最大工資。
#include
#include
#include
using namespace std;
struct job
{
int s, e, c;
}a[1005];
int dp[1005];
bool comp(job a1, job a2)
{
if(a1.e != a2.e)
return a1.e < a2.e;
if(a1.s != a2.s)
return a1.s > a2.s;
return a1.c > a2.c;
}
int main()
{
int t, n, m, c, s, e, i, j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
memset(dp, 0, sizeof(dp));
int k = 0;
for(i = 0; i < n; i++)
{
scanf("%d%d%d",&s, &e, &c);
if(s >= 1 && e <= m)
{
a[k].s = s;
a[k].e = e;
a[k++].c = c;
}
}
sort(a, a+k, comp);
for(i = 0; i < k; i++)
{
if(dp[a[i].s - 1] + a[i].c > dp[a[i].e]) //做第i個工作能獲得更多的工資
{
for(j = a[i].e; j <= m; j++) //更新後面的工資
dp[j] = a[i].c + dp[a[i].s - 1];
}
}
printf("%d\n",dp[m]);
}
return 0;
}
/*dp[i]表示到第i天結束時能夠得到的最大工資*/
