首页 > ACM题库 > HDU-杭电 > HDU 3043- Number game-枚举-[解题报告]HOJ
2014
02-27

HDU 3043- Number game-枚举-[解题报告]HOJ

Number game

问题描述 :

One day, QQ is playing a number game. He first sorts the N numbers 1, 2, 3…n, but this is too easy. So long1 wants to challenge QQ’s skill, he let the number sequence becomes wavy. For example, a1<a2>a3<a4>a5… or a1>a2<a3>a4<a5….
Now long1 sorts these wavy sequences by lexicographic order, and he wants to know what the M-th sequence is when you have N numbers.
As an Acmer, long1 thinks you can solve it and gives him the answer.

输入:

There are many test cases:
For every case:

First line is the number of case
The next case lines:
Every line contains two numbers N, and M.(1<=N<=20,M is not larger than the number of wavy sequences)

输出:

There are many test cases:
For every case:

First line is the number of case
The next case lines:
Every line contains two numbers N, and M.(1<=N<=20,M is not larger than the number of wavy sequences)

样例输入:

2 
2 1 
3 3 

样例输出:

1 2 
2 3 1 
Hint
Hint: You can assume that the number of total wavy sequences will not beyond INT64.

/*

题目:
    每一天都只能每一种鱼,并且买了这种鱼后,在以后每周的该天都得买那种鱼。
    另外如果某一天没买鱼的话,就不能在以后买鱼了(已被饿死。。。)。现在
    给出n天每一种鱼的价格,并且给出你拥有的价钱,问你什么时候不能再买鱼了

分析:
    map[i,j]表示从第一天开始买了j种鱼到i天时所用的总价钱。然后从后面开始枚举
    答案,枚举一周内每天所使用的价钱总和若不大于你拥有的金钱时就输出答案

*/
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int X = 10002;
const int maxn = 51;

int map[X][maxn];
int n,m,budge;

int main()
{
    freopen("sum.in","r",stdin);
    while(cin>>n>>m>>budge)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                scanf("%d",&map[i][j]);
        for(int i=7;i<n;i++)
            for(int j=0;j<m;j++)
                map[i][j] += map[i-7][j];
        int ans;
        int sum = 0;
        for(ans=n;ans>0;ans--)
        {
            sum = 0;
            for(int i=ans-1;i>=0&&i>=ans-7;i--)
            {
                int MIN = 1e9;
                for(int j=0;j<m;j++)
                    MIN = min(MIN,map[i][j]);
                if(MIN>budge)
                {
                    sum = 1e9;
                    break;
                }
                sum += MIN;
                if(sum>budge)
                    break;
            }
            if(sum<=budge)
                break;
        }
        cout<<ans<<endl;
    }
    return 0;
}

参考:http://www.cnblogs.com/yejinru/archive/2012/07/25/2608077.html


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?