POJ 1949 Chores (很难想到的dp)
传送门:
http://poj.org/problem?id=1949
Time Limit: 3000MS | Memory Limit: 30000K | |
Total Submissions: 6368 | Accepted: 3013 |
Description
Farmer John has a list of N (3 <= N <= 10,000) chores that must be completed. Each chore requires an integer time (1 <= length of time <= 100) to complete and there may be other chores that must be completed before this chore is started. We will call these prerequisite chores. At least one chore has no prerequisite: the very first one, number 1. Farmer John's list of chores is nicely ordered, and chore K (K > 1) can have only chores 1,.K-1 as prerequisites. Write a program that reads a list of chores from 1 to N with associated times and all perquisite chores. Now calculate the shortest time it will take to complete all N chores. Of course, chores that do not depend on each other can be performed simultaneously.
Input
* Lines 2..N+1: N lines, each with several space-separated integers. Line 2 contains chore 1; line 3 contains chore 2, and so on. Each line contains the length of time to complete the chore, the number of the prerequisites, Pi, (0 <= Pi <= 100), and the Pi prerequisites (range 1..N, of course).
Output
Sample Input
7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6
Sample Output
23
Hint
[Here is one task schedule:
Chore 1 starts at time 0, ends at time 5.
Chore 2 starts at time 5, ends at time 6.
Chore 3 starts at time 6, ends at time 9.
Chore 4 starts at time 5, ends at time 11.
Chore 5 starts at time 11, ends at time 12.
Chore 6 starts at time 11, ends at time 19.
Chore 7 starts at time 19, ends at time 23.
]
Source
#include <iostream>
#include <stdio.h>
#include<memory>
#include<stack>
#include<string.h>
#include<algorithm>
using namespace std;
#define max_v 11000
int dp[max_v];//表示执行到第i个任务所需要的最小时间
//每次DP[i]应该等于完成之前优先任务的最大时间
int main()
{
int n,x,y,k,ans=;
dp[]=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d %d",&x,&k);
if(k>)
{
for(int j=;j<=k;j++)
{
scanf("%d",&y);
dp[i]=max(dp[i],dp[y]+x);
}
}else
{
dp[i]=x;
}
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
return ;
}
最新文章
- 基于@AspectJ配置Spring AOP之一--转
- 增强for循环(forearch)
- [codeforces 317]A. Perfect Pair
- Sql Server来龙去脉系列 必须知道的权限控制基础篇
- IDEA SDK(Software Development Kit) 介绍
- STM32之GPIO端口位带操作
- .NET设计模式(14):代理模式(Proxy Pattern)(转)
- backbone showcase
- PHP中定义常量define与const
- python学习笔记(一)之入门
- BP算法的矩阵推导
- Android:真机调试遇到的问题(You need to use a Theme.AppCompat theme (or descendant) with this activity)
- Windows DHCP备份还原命令
- [ASP.NET]初试Web API
- Python小白学习之路(十六)—【内置函数一】
- 每日英语:The Upside of Favoritism
- C# 一些常用的字符串扩展方法
- 【原创】java 获取十个工作日之前或之后的日期(算当天)-完美解决-费元星
- 第K层的结点数
- linux下安装composer