首页 > ACM题库 > HDU-杭电 > hdu 2599 The Dreadful Seven[解题报告]C++
2014
02-10

hdu 2599 The Dreadful Seven[解题报告]C++

The Dreadful Seven

问题描述 :

Super Mario is studying how to use a mysterious Power Square. The Power Square is n×n with integer values between 0 and n2-1.
A number y is a neighbor of another number x in the Power Square if y is directly above or below x, or directly to the left or right of x. Rosalina asks Super Mario to find all the numbers in the Power Square that are neighbors of the number 7, since she can tell that those numbers are quite nervous.
”Why are the numbers scared of seven?” Mario asks Rosalina.
”Because seven ate nine!” Rosalina exclaims.

输入:

Input is a description of of the Power Square, followed by a number of commands. The first line is the size of the Power Square n. You may assume n<=100. The second line contains the n2 values in the Power Square, separated by spaces. Values start from the top left corner and move from left to right, moving down one row to the leftmost position when a row is filled.
Following the Power Square description are a number of commands, with each command on a separate line. Each command begins with the name of the command, followed by any additional command parameters.
There will no more than 100 commands.

输出:

Input is a description of of the Power Square, followed by a number of commands. The first line is the size of the Power Square n. You may assume n<=100. The second line contains the n2 values in the Power Square, separated by spaces. Values start from the top left corner and move from left to right, moving down one row to the leftmost position when a row is filled.
Following the Power Square description are a number of commands, with each command on a separate line. Each command begins with the name of the command, followed by any additional command parameters.
There will no more than 100 commands.

样例输入:

3
8 7 6 5 4 3 2 1 0
SHOW
NEIGHBORS 7
NEIGHBORS 1
NEIGHBORS 4
4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
SHOW
NEIGHBORS 7
NEIGHBORS 1
NEIGHBORS 8
NEIGHBORS 14

样例输出:

8 7 6
5 4 3
2 1 0

8 6 4
4 2 0
7 5 3 1
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

3 6 11
0 2 5
4 9 12
10 13 15

该题就用反方向思考,就是p = 1.0 -p 就可以了,不安全系数变成安全系数,再把安全系数相乘就可以了;

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int ZeroOnepack( double pro[] ,int value[],double p ,int N, int sum )
{
    double f[10024] ={ 1.0 };
    for( int i = 0 ; i < N;  i++ )
    {
        for( int  j = sum ; j >= value[i] ; j -- )
        {
            if( f[j] < f[j - value[i]] * pro[i])
                f[j] = f[j - value[i]] * pro[i];     
        }     
    }
    for( int i = sum ; i >=0 ; i -- )
    {
       if( f[i] >= p )
          return i;  
    }   
}
int main( )
{
    int value[1024],N,Case,num;
    double p,pro[1024];
    while( scanf( "%d" ,&Case )==1 )
    {
        while( Case-- )
        {
            int sum = 0 ;
            scanf( "%lf%d",&p , &N );
            for( int i = 0 ; i < N; i++ )
            {
               scanf( "%d%lf" ,&value[i] , &pro[i] );
               pro[i] = 1.0 - pro[i];
               sum += value[i];   
            }
            printf( "%d\n",ZeroOnepack( pro , value,1.0- p, N,sum ) );
        }       
    }
    return 0;    
}

 

解题转自:http://www.cnblogs.com/bo-tao/archive/2012/03/10/2389196.html


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }