P2876 [USACO07JAN]解决问题Problem Solving

    • 99通过
    • 214提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 最短路 贪心 USACO 2007
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    In easier times, Farmer John's cows had no problems. These days, though, they have problems, lots of problems; they have P (1 ≤ P ≤ 300) problems, to be exact. They have quit providing milk and have taken regular jobs like all other good citizens. In fact, on a normal month they make M (1 ≤ M ≤ 1000) money.

    Their problems, however, are so complex they must hire consultants to solve them. Consultants are not free, but they are competent: consultants can solve any problem in a single month. Each consultant demands two payments: one in advance (1 ≤ payment ≤ M) to be paid at the start of the month problem-solving is commenced and one more payment at the start of the month after the problem is solved (1 ≤ payment ≤ M). Thus, each month the cows can spend the money earned during the previous month to pay for consultants. Cows are spendthrifts: they can never save any money from month-to-month; money not used is wasted on cow candy.

    Since the problems to be solved depend on each other, they must be solved mostly in order. For example, problem 3 must be solved before problem 4 or during the same month as problem 4.

    Determine the number of months it takes to solve all of the cows' problems and pay for the solutions.

    P个问题,雇佣相同的人去解决,每个人每月解决一道题,每个人解决问题的代价都分两次,解决问题当月给a[i],事后第二月给b[i],然后每个月有m的钱,问最快多久解决所有问题。(问题必须按照序号一个个解决) 这个月用上个月的钱支付,然后结余会用来买糖

    输入输出格式

    输入格式:

    Line 1: Two space-separated integers: M and P.

    Lines 2..P+1: Line i+1 describes problem i with two space-separated integers: Bi and Ai. Bi is the payment to the consult BEFORE the problem is solved; Ai is the payment to the consult AFTER the problem is solved.

    输出格式:

    Line 1: The number of months it takes to solve and pay for all the cows' problems.

    输入输出样例

    输入样例#1: 复制
    100 5
    40 20
    60 20
    30 50
    30 50
    40 40
    输出样例#1: 复制
    6

    说明

    +------+-------+--------+---------+---------+--------+

    |      | Avail | Probs  | Before  | After   | Candy  | |Month | Money | Solved | Payment | Payment | Money  | +------+-------+--------+---------+---------+--------+

    | 1    | 0     | -none- | 0       | 0       | 0      | | 2    | 100   | 1, 2   | 40+60   | 0       | 0      | | 3    | 100   | 3, 4   | 30+30   | 20+20   | 0      | | 4    | 100   | -none- | 0       | 50+50   | 0      | | 5    | 100   | 5      | 40      | 0       | 60     | | 6    | 100   | -none- | 0       | 40      | 60     | +------+-------+--------+---------+---------+--------+

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。