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];
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
- 梦里不知身是客,不堪回首月明中什么意思
- 五年级一班有42人,二班有48人,把360本图书按人数分给两个班,二班分多少本
- 有两个桶,一个能装3升水,一个能装5升水,怎样才能能准确称出4升水?
- 一个数乘上0.32的积比3的5倍少12.44,求这个数.用解方程计算.
- 已知圆锥的底面半径为4,高为6,在其中有一个高为x的内接圆柱,设圆柱的侧面积为y
- How long did you Spend (do) your home
- Y求一道数学题,题目是今天是周五,从今天算起第21天是周几,
- 按下面的摆法摆80个三角形,一共有多少个白色的三角形?
- 汉译英两个词组
- 描写春天、夏天、秋天、冬天小树像什么?
热门考点
- 单糖、二糖、多糖的化学式.
- AB是圆0的直径,PA垂直于圆0所在的平面,C是圆周上不同于A,B的任意一点,求证平面PAC垂直平面PBC
- 问价钱不是用How much吗?这里为什么用what?
- 将在外,君命有所不受.这句话是谁最早提出来的
- 两个长方形重叠的面积相当于大长方形面积的1/7,相当于小肠房型面积的1/5,阴影部分的面积为200cm²,
- 将11.2克的Mg和Cu混合物完全溶解与足量的硝酸中收集反应产生的X气体.在向所得的溶液中加入过量的NaOH溶
- what do you do 跟what are you
- There is a newspaper on the desk以a newspaper提问
- 写出一个不等式满足它的整数解为-1,0,1
- 欲观察细胞减数分裂的过程,可选用的材料为何是蝗虫的精巢?