本文主要是介绍hdu 4502 吉哥系列故事——临时工计划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
第三题:先排序dp[i]=max{dp[i-1],dp[i - (e -s+1)]+c}
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 100000000
int dp[105];
struct Node{int s,e,c;
}node[1005];
bool cmp(Node a, Node b)
{if(a.e == b.e)return a.s < b.s;return a.e < b.e;
}
int main()
{int T, n, m;for(scanf("%d", &T); T--;){scanf("%d%d", &n, &m);for(int i = 0; i < m; ++i)scanf("%d%d%d", &node[i].s, &node[i].e, &node[i].c);sort(node, node + m, cmp);dp[0] = 0;int j = 0;node[m].e = INF;for(int i = 1; i <= n; ++i){dp[i] = dp[i - 1];while(node[j].e == i){int temp;if((i >= (temp = (node[j].e - node[j].s) + 1)) && (dp[i] <(temp = ( dp[i - temp] + node[j].c))))dp[i] = temp;++j;}}printf("%d\n",dp[n]);}return 0;
}
这篇关于hdu 4502 吉哥系列故事——临时工计划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!