2010年7月21日 #

# 题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=2571                                               命运

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 998    Accepted Submission(s): 336

Problem Description

yifenfei一开始在左上角，目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒，所以每个格子都对应一个值，走到那里便自动得到了对应的值。

Input

Output

Sample Input
```1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10
```

Sample Output
```52
```

Author
yifenfei

Source
ACM程序设计期末考试081230

Recommend
yifenfei

Statistic | Submit | Discuss | Back

DP

posted @ 2010-07-21 11:16 wei 阅读(464) | 评论 (0)编辑 收藏

2010年7月20日 #

# How many ways

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 446    Accepted Submission(s): 304

Problem Description

1.机器人一开始在棋盘的起始点并有起始点所标有的能量。
2.机器人只能向右或者向下走，并且每走一步消耗一单位能量。
3.机器人不能在原地停留。
4.当机器人选择了一条可行路径后，当他走到这条路径的终点时，他将只有终点所标记的能量。

Input

Output

Sample Input
```1
6 6
4 5 6 6 4 3
2 2 3 1 7 2
1 1 4 6 2 7
5 8 4 3 9 5
7 6 6 2 1 5
3 1 1 3 7 2
```

Sample Output
```3948
```

Author
xhd

Source
2008杭电集训队选拔赛

DP

posted @ 2010-07-20 19:37 wei 阅读(384) | 评论 (0)编辑 收藏

# Super Jumping! Jumping! Jumping!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6529    Accepted Submission(s): 2569

Problem Description
Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now.

The game can be played by two or more than two players. It consists of a chessboard（棋盘）and some chessmen（棋子）, and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path.
Your task is to output the maximum value according to the given chessmen list.

Input
Input contains multiple test cases. Each test case is described in a line as follow:
N value_1 value_2 …value_N
It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int.
A test case starting with 0 terminates the input and this test case is not to be processed.

Output
For each case, print the maximum according to rules, and one line one case.

Sample Input
```3 1 3 2
4 1 2 3 4
4 3 3 2 1
0
```

Sample Output
```4
10
3
```
最大递增子段和,状态方程:sum[j]=max{sum[i]}+a[j]; 其中,0<=i<=j,a[i]<a[j]
hdu1087

posted @ 2010-07-20 18:32 wei 阅读(2759) | 评论 (2)编辑 收藏

## 数塔(经典的dp hdu 2084)

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=2084

# 数塔

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4634    Accepted Submission(s): 2744

Problem Description

Input

Output

Sample Input
```1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
```

Sample Output
```30
```

Source

posted @ 2010-07-20 17:09 wei 阅读(454) | 评论 (0)编辑 收藏

2010年7月18日 #

# DFS

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1228    Accepted Submission(s): 724

Problem Description
A DFS(digital factorial sum) number is found by summing the factorial of every digit of a positive integer.

For example ,consider the positive integer 145 = 1!+4!+5!, so it's a DFS number.

Now you should find out all the DFS numbers in the range of int( [1, 2147483647] ).

There is no input for this problem. Output all the DFS numbers in increasing order. The first 2 lines of the output are shown below.

Input
no input

Output
Output all the DFS number in increasing order.

Sample Output
```						1
2
......
```

1 // 打表的代码，就是将范围之内的全部举出来即可以
2 /*
3 #include<iostream>
4 #define MAX 5
5 using namespace std;
6 int data[MAX];
7 int main()
8 {
9 data[0]=1;
10 data[1]=2;
11 data[2]=145;
12 data[3]=40585;
13 int i;
14 for(i=0;i<=3;i++)
15 cout<<data[i]<<endl;
16 return 0;
17 } */

18
19 #include < iostream >
20 using   namespace  std;
21 int  f[ 11 ];
22 void  dfs( int  n) // 深搜,判断n是否是DFS数
23 {
24      // 拿到一个数将要把它的每一位得到,从个位开始
25      int  sum = 0 ,x = n; // 要保留住n
26      while (x)
27      {
28         sum += f[x % 10 ]; // 得到每一位直接求得阶层
29         x /= 10 ;
30     }

31      if (sum == n) // 如果每一位的阶层之和和n相同则return true;
32      {
33         cout << n << endl;
34     }

35 }

36 int  main()
37 {
38     memset(f, 0 , sizeof (f)); // 初始化
39      int  i;
40     f[ 0 ] = 1 ;
41      for (i = 1 ;i <= 10 ;i ++ ) // 得到个位的阶层
42         f[i] = i * f[i - 1 ];
43      for (i = 1 ;i <= 2147483647 ;i ++ )
44         dfs(i);
45      return   0 ;
46 }

posted @ 2010-07-18 23:59 wei 阅读(230) | 评论 (0)编辑 收藏

## H__恶魔猎手会飞了(2009年院赛题目（有关搜索题目------bfs广搜试手）)

摘要: H__恶魔猎手会飞了 Time Limit:3000MS  Memory Limit:65536KTotal Submit:60 Accepted:15 Description 恶魔猎手成功拿到了古尔丹之颅，吸收了古尔丹之颅的力量后，恶魔猎手全身变的一片漆黑，后背上也长出了一对翅膀，也就是说：他会飞了！！ 兴奋...  阅读全文

posted @ 2010-07-18 20:08 wei 阅读(325) | 评论 (0)编辑 收藏

# Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5409    Accepted Submission(s): 2402

Problem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input
n (0 < n < 20).

Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

Sample Input
```						6
8
```

Sample Output
```						Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
```

Source

posted @ 2010-07-18 14:13 wei 阅读(500) | 评论 (0)编辑 收藏

## Fire Net

Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.

A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.

Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.

The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.

The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.

The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file.

For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.

Sample input:

```4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0
```

Sample output:

```5
1
5
2
4
Fire Net 1#include<iostream> 2using namespace std; 3 4char map[4][4];//地图 5int n,maxsum; 6 7bool canput(int row,int col)//判断这点是否可以放置堡垒 8{ 9    int i,j;10    //测试是否可以放碉堡，就是是否有危险11    12    //先测试col列方向上的13    14    for(i=row-1;i>=0;--i)15    {16        if(map[i][col]=='O')//如果这列上有碉堡17            return false;18        if(map[i][col]=='X') break;//如果先遇到的是墙即可以放19        20    }21    //从row行方向上的22    for(j=col-1;j>=0;--j)23    {24        if(map[row][j]=='O')25            return false;26        if(map[row][j]=='X')27            break;28        29    }30    return true;31    32    33}3435void dfs(int k,int num)//深搜的关键,行向走的，先遍历完一行再遍历一行36{37    int x,y;//代表行号和列号38    if(k==n*n)//终止条件39    {40        if(maxsum<num)41        {42            maxsum=num;43            return ;44        }45    }46    else 47    {48        x=k/n;//行号49        y=k%n;//列号50        51        //满足条件可以放堡垒52        if((map[x][y]=='.')&&(canput(x,y)==true))53        {54            //当前点是空白处，并且可以放置碉堡55            map[x][y]='O';//代替了visit[x][y]==1,来放置堡垒56            dfs(k+1,num+1);//进入下一个递归,由于满足条件可以放置堡垒，所以num+157            map[x][y]='.';//回溯58            59        }60        dfs(k+1,num);//有两种用途一种是没有满足条件的递归，还有一种是回溯以后的递归61    }    62    63}64int main()65{66    int i,j;67    while( cin>>n && n )68    {69        //输入地图的数据70        for(i=0;i<n;i++)71        {72            getchar();73            for(j=0;j<n;j++)74                cin>>map[i][j];75        }76        //初始化77        maxsum=0;78        //开始深搜79        dfs(0,0);//从第一个结点开始搜索80        cout<<maxsum<<endl;    81    }82    83    return 0;84}```

posted @ 2010-07-18 12:58 wei 阅读(362) | 评论 (0)编辑 收藏

2010年7月11日 #

# Ignatius and the Princess III

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3088    Accepted Submission(s): 2133

Problem Description
"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.

"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"

Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.

Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.

Sample Input
```						4
10
20
```

Sample Output
```						5
42
627
```

Author
Ignatius.L

posted @ 2010-07-11 00:30 wei 阅读(895) | 评论 (0)编辑 收藏

2010年7月10日 #

# Max Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 38854    Accepted Submission(s): 8400

Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input
```						2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
```

Sample Output
```						Case 1:
14 1 4

Case 2:
7 1 6
```

Author
Ignatius.L

posted @ 2010-07-10 16:38 wei 阅读(546) | 评论 (0)编辑 收藏