加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

POJ PKU 1949 动态规划

(2010-04-23 16:08:18)
标签:

poj

pku

1949

it

分类: 动态规划

题目描述:

有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()
{
    scanf("%d", &n);
    ans = dp[0] = 0;
    for(int i = 1; i <= n; i )
    {
        scanf("%d%d", &x, &len);mmin = 0;
        while(len--)
        {
            scanf("%d", &y);
            if (dp[y] > mmin) mmin = dp[y];
        }
        if ((dp[i] = mmin x) > ans) ans = dp[i];
    }
    printf("%d\n", ans);
    return 0;
}

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有