首页 > ACM题库 > HDU-杭电 > hdu 1920 Jackpot-动态规划-[解题报告]C++
2013
12-25

hdu 1920 Jackpot-动态规划-[解题报告]C++

Jackpot

问题描述 :

Bill has found the perfect way to make money playing the slot machines. After months of careful research, he has finally figured out the mechanics behind how the machines operate. Now he is ready to make profit of his findings.

But first an introduction to the game. A slot machine consists of a number of wheels, usually three or four, each with a number of symbols printed on it � cherries, oranges, bells, etc. � and will show one of its symbols at a given time. To play, you insert a coin, push a button and
the wheels start spinning. After spinning for a while, each wheel stops � at random it seems � at one of its symbols. If all wheels stop at the same symbol, or some nice combination of symbols, the player wins. One combination that is especially desirable is having the jackpot symbol on all wheels. This combination is simply called ’jackpot’ and will make you rich for life.

What Bill has discovered is that each wheel will stop at the jackpot symbol with a certain periodicity, which differs a lot between wheels. He has also figured out (after some sneeking around at the slot-machine factory) that all newly manufactured slot-machines are delivered showing the jackpot combination, and that they all have a counter at the back, telling how many times the machine has been played. This counter is always set to zero at delivery.

Now, all Bill needs to do is to calculate the number of times a machine has to be played between two occurrences of the jackpot combination. We will call this number the jackpot periodicity. This is of course the same as the number of times the machine has to be played after leaving the factory, before it gives its first jackpot. Thus, with a glance at the counter on the back of a machine, Bill can figure out if it is about to give a jackpot. As Bill knows that you are a skillful computer programmer, he turns to you with the problem of calculating the jackpot periodicity. For each machine, he will give you the number of wheels, and the periodicity with
which the jackpot symbol shows up on each wheel.

输入:

One line with the number of machines n <= 20. For each machine, one line with the number of wheels w <= 5, and one line with w numbers, p1,p2,….pw,the periodicity of each wheel pk<=1000.

输出:

One line with the number of machines n <= 20. For each machine, one line with the number of wheels w <= 5, and one line with w numbers, p1,p2,….pw,the periodicity of each wheel pk<=1000.

样例输入:

1
3
10 6 15

样例输出:

30

DP有点刷不动了,只好再看看书和资料补一补。

本着日A一题的原则,今天刷了一道水题。

最大子段和的问题。

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    int n,a;
    while(scanf("%d",&n)&&n)
    {
        int sum=0,mx=0;
        for(int i=0; i<n; ++i)
        {
            scanf("%d",&a);
            if(sum<0)
                sum=a;
            else sum+=a;
            if(sum>mx) mx=sum;
        }
        if(mx>0)
            printf("The maximum winning streak is %d.\n",mx);
        else
            printf("Losing streak.\n");
    }
    return 0;
}

解题转自:http://blog.csdn.net/kkkwjx/article/details/11495183


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯