首页 > ACM题库 > HDU-杭电 > hdu 2264 The best riding route待解决[解题报告]C++
2014
01-04

hdu 2264 The best riding route待解决[解题报告]C++

The best riding route

问题描述 :

As a cheap labor in a small company, LL has to ride back and forth between school and office every day. It is a tedious trip. So he want to design the most satisfactory riding route. After several day’s experiment, he draw the simple map. It contains n*m areas. The school is in (0,0) while the office is in (n-1,m-1). He also record the scenery rank of each area A(i,j) and the time need to ride through each area B(i,j). ( For the start and end, A(0,0), B(0,0), A(n-1,m-1), B(n-1,m-1) are always 0. ) Now, LL defines the satisfactory degree of a round trip as follow:

                                       ∑{ A(i,j) | Area (i,j) is in the riding route (come or go). }
the satisfactory degree = ———————————————————————-
                                       ∑{ B(i,j) | Area (i,j) is in the riding route (come or go). }

Attention: 1. LL doesn’t want to make a detour. So, from school to office he only ride rightward or downward and from office to school only leftward or upward.
                2. LL won’t pass the same area in the whole round trip except the start and end.

输入:

Each test case begins with two integers n,m ( 3<=n,m<=30 ), which is the size of the map. Then n lines follow, each contains m integers A(i,j). Another n lines follow, each contains m integers B(i,j). 1 <= A(i,j),B(i,j) <= 100.

输出:

Each test case begins with two integers n,m ( 3<=n,m<=30 ), which is the size of the map. Then n lines follow, each contains m integers A(i,j). Another n lines follow, each contains m integers B(i,j). 1 <= A(i,j),B(i,j) <= 100.

样例输入:

3 3
0 1 2
3 4 5
6 7 0
0 7 6
5 4 3
2 1 0

样例输出:

13/11

Hint
The best riding route is (0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(1,2)->(1,1)->(0,1)->(0,0).


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。