POJ PKU 1949 动态规划
(2010-04-23 16:08:18)
标签:
pojpku1949it |
分类: 动态规划 |
题目描述:
有n个任务,第i个任务需要时间xi来完成,并且第i个任务必须在它 “前面的” 某些任务完成之后才能开始。
给你任务信息,问你最短需要多少时间来完成任务。
解题报告:
“前面的”,知道这些任务已经是top排序好的了。
dp[i] = 完成第i个任务时所需的最短的时间。
dp[i] = max(dp[j]) xi, j是需要在它前面完成的任务的序号。
max(dp[i])就是答案。
代码如下:
#include<iostream>
using namespace std;
int n, dp[10004], len, x, y, mmin, ans;
int main()
{
}