美妙的acm

记录acm历程

2010年7月21日 #

命运(经典DP--hdu2571)

题目来源: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
穿过幽谷意味着离大魔王lemon已经无限接近了!
可谁能想到,yifenfei在斩杀了一些虾兵蟹将后,却再次面临命运大迷宫的考验,这是魔王lemon设下的又一个机关。要知道,不论何人,若在迷宫中被困1小时以上,则必死无疑!
可怜的yifenfei为了去救MM,义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧!
命运大迷宫可以看成是一个两维的方格阵列,如下图所示:

yifenfei一开始在左上角,目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒,所以每个格子都对应一个值,走到那里便自动得到了对应的值。
现在规定yifenfei只能向右或者向下走,向下一次只能走一格。但是如果向右走,则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子,即:如果当前格子是(x,y),下一步可以是(x+1,y),(x,y+1)或者(x,y*k) 其中k>1。
为了能够最大把握的消灭魔王lemon,yifenfei希望能够在这个命运大迷宫中得到最大的幸运值。

 

Input
输入数据首先是一个整数C,表示测试数据的组数。
每组测试数据的第一行是两个整数n,m,分别表示行数和列数(1<=n<=20,10<=m<=1000);
接着是n行数据,每行包含m个整数,表示n行m列的格子对应的幸运值K ( |k|<100 )。
 

Output
请对应每组测试数据输出一个整数,表示yifenfei可以得到的最大幸运值。
 

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 阅读(374) | 评论 (0)编辑 收藏

2010年7月20日 #

How many ways(DP题目---hdu1978)

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

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,1)走到棋盘的终点(n,m)。游戏的规则描述如下:
1.机器人一开始在棋盘的起始点并有起始点所标有的能量。
2.机器人只能向右或者向下走,并且每走一步消耗一单位能量。
3.机器人不能在原地停留。
4.当机器人选择了一条可行路径后,当他走到这条路径的终点时,他将只有终点所标记的能量。

如上图,机器人一开始在(1,1)点,并拥有4单位能量,蓝色方块表示他所能到达的点,如果他在这次路径选择中选择的终点是(2,4)

点,当他到达(2,4)点时将拥有1单位的能量,并开始下一次路径选择,直到到达(6,6)点。
我们的问题是机器人有多少种方式从起点走到终点。这可能是一个很大的数,输出的结果对10000取模。
 

Input
第一行输入一个整数T,表示数据的组数。
对于每一组数据第一行输入两个整数n,m(1 <= n,m <= 100)。表示棋盘的大小。接下来输入n行,每行m个整数e(0 <= e < 20)。
 

Output
对于每一组数据输出方式总数对10000取模的结果.
 

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 阅读(273) | 评论 (0)编辑 收藏

Super Jumping! Jumping! Jumping!(dp经典题目hdu 1087)

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

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 阅读(2558) | 评论 (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
在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的:

有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?

已经告诉你了,这是个DP的题目,你能AC吗?
 

Input
输入数据首先包括一个整数C,表示测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间[0,99]内。
 

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 阅读(350) | 评论 (0)编辑 收藏

2010年7月18日 #

DFS(交的时候有点问题)


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 阅读(122) | 评论 (0)编辑 收藏

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

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

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

Prime Ring Problem(经典的搜索题目)

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 阅读(372) | 评论 (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

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

2010年7月11日 #

Ignatius and the Princess III(杭电1028(动态规划))

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 阅读(725) | 评论 (0)编辑 收藏

2010年7月10日 #

Max Sum(杭电1003(动态规划))

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 阅读(385) | 评论 (0)编辑 收藏

仅列出标题  下一页

My Links

留言簿

随笔档案

最新随笔

搜索

最新评论