acm编程题:会议安排,只要给出思路

题目

acm编程题:会议安排,只要给出思路
只要给出解题思路和编程实现思路,
会议安排
Time Limit:1000MS Memory Limit:65536KB
Total Submit:406 Accepted:89
Description
科研人员与相关领域的国内外同行进行适时的接触与充分的交流,对于促进提高他们的科研业务水平,并及时掌握科研动态是十分必要而且重要的.ECNU为了走在科技的前沿,于是决定派遣一些学者出去参加会议.由于这些会议具有不同的级别,因此对于科研人员可能带来的科研上的促进作用也就可能不同.但是一个学者不能同时参加两个会议.而且,如果一个学者需要连续参加两个会议,第二个会议的开始时间要晚于第一个会议的结束时间..
现在给出一些会议的起始时间和终止时间,并给出这些会议对应的促进值,请你计算出一个学者能够得到的最大的促进值.
Input
第一行为一个整数T,表示测数数据的组数.
每组数据第一行为整数n(1

答案

解答本题需要一定的动态规划知识.

vector<pair<int, int>> pre[i];
// pre[i][j]表示第j个在i时刻结束的会议
// pre[i][j].first表示这个会议的开始时间,pre[i][j].second表示这个会议的结束时间
int dp[366] = {};
// dp[t]表示0到t时刻最多能得到的促进值的和
for (int t = 0; t <= 365; ++t) {
  if (t > 0 && dp[t] < dp[t - 1]) {
    dp[t] = dp[t - 1];
  }
  for (unsigned j = 0; j < pre[i].size(); ++j) {
    int s = pre[t][j].first, w = pre[t][j].second;
    int pre_w = s == 0 ? 0 : dp[s - 1];
    if (pre_w + w > dp[t]) {
      dp[t] = pre_w + w;
    }
  }
}
return dp[365];