ural 1119 Metro dp水

点击打开链接

1119. Metro

Time limit: 0.5 second

Memory limit: 64 MB

Many of SKB Kontur programmers like to get to work by Metro because the main office is situated quite close the station Uralmash. So, since a sedentary life requires active exercises off-duty, many
of the staff — Nikifor among them — walk from their homes to Metro stations on foot.

Nikifor lives in a part of our city where streets form a grid of residential quarters. All the quarters are squares with side 100 meters. A Metro entrance is situated at one of the crossroads. Nikifor
starts his way from another crossroad which is south and west of the Metro entrance. Naturally, Nikifor, starting from his home, walks along the streets leading either to the north or to the east. On his way he may cross some quarters diagonally from their
south-western corners to the north-eastern ones. Thus, some of the routes are shorter than others. Nikifor wonders, how long is the shortest route.

You are to write a program that will calculate the length of the shortest route from the south-western corner of the grid to the north-eastern one.

Input

There are two integers in the first line: N and M (0 < N,M ≤ 1000) — west-east and south-north sizes of the grid. Nikifor starts his way from a crossroad which is
situated south-west of the quarter with coordinates (1, 1). A Metro station is situated north-east of the quarter with coordinates (NM). The second input line contains a number K (0 ≤ K ≤ 100) which is a number of quarters
that can be crossed diagonally. Then K lines with pairs of numbers separated with a space follow — these are the coordinates of those quarters.

Output

Your program is to output a length of the shortest route from Nikifor‘s home to the Metro station in meters, rounded to the integer amount of meters.

Sample

input output
3 2
3
1 1
3 2
1 2
383

Problem Author: Leonid Volkov

Problem Source: USU Open Collegiate Programming Contest October‘2001 Junior Session

从左下角的点走到右上角的点最少可以走多少步,其中有的点可以走对角线。

第一行和第一列的点肯定无法从对角线得来,所以可以初始化。对于其余的点,有的可以从其左面或者下面得来,有的还可以从对角线得来,只要求最小即可。

状态转移方程:

如果可以从左面或者下面得来的点:dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);

如果可以从左面或者下面或者对角线得来的点:dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+P));

开了3层for循环,原本以为会超时,1000*1000*100。结果跑了0.1568s,也是醉了。

//0.156	8 110 KB
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define P sqrt(2)
using namespace std;
double dp[1007][1007];
struct N
{
    int x,y;
}p[107];
int cmp(N a,N b)
{
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
	    n++;m++;
        int k;
        scanf("%d",&k);
        for(int i=0;i<k;i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        sort(p,p+k,cmp);
        dp[1][1]=0;
        for(int i=2;i<=n;i++)//初始化第一行
            dp[i][1]=dp[i-1][1]+1;
        for(int i=2;i<=m;i++)//初始化第一列
            dp[1][i]=dp[1][i-1]+1;
        for(int i=2;i<=n;i++)
            for(int j=2;j<=m;j++)
            {
                int flag=0;
                for(int a=0;a<k;a++)
                    if(p[a].x==(i-1)&&p[a].y==(j-1))//从三个方向得来
                        {dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+P));flag=1;break;}
                    else if(p[a].x>(i-1))break;
                if(!flag)dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);//从两个方向得来
            }
        printf("%.lf\n",dp[n][m]*100);
	}
	return 0;
}

时间: 01-09

ural 1119 Metro dp水的相关文章

递推DP URAL 1119 Metro

题目传送门 1 /* 2 题意:已知起点(1,1),终点(n,m):从一个点水平或垂直走到相邻的点距离+1,还有k个抄近道的对角线+sqrt (2.0): 3 递推DP:仿照JayYe,处理的很巧妙,学习:) 4 好像还要滚动数组,不会,以后再补 5 */ 6 #include <cstdio> 7 #include <iostream> 8 #include <algorithm> 9 #include <cmath> 10 #include <cs

Ural 1119 Metro(DP)

题目地址:Ural 1119 因为还有一个可不可以穿的问题,所以需要再加一维.0代表可穿不可穿,可穿设置成0,不可穿就设置成无穷大.1代表当前这格的最短距离. 代码如下: #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h

URAL 1039 Anniversary Party 树形DP 水题

1039. Anniversary Party Time limit: 0.5 secondMemory limit: 8 MB Background The president of the Ural State University is going to make an 80'th Anniversary party. The university has a hierarchical structure of employees; that is, the supervisor rela

URAL 1244 Gentlement DP +记录路径 好题

1244. Gentlemen Time limit: 0.5 secondMemory limit: 64 MB Let's remember one old joke: Once a gentleman said to another gentleman:— What if we play cards?— You know, I haven't played cards for ten years…— And I haven't played for fifteen years…So, li

UVA 1025 A Spy in the Metro DP

DP[ i ][ j ] 在 i 时刻 j 号车站的等待最小时间..... 有3种可能: 在原地等,坐开往左边的车,做开往右边的车 A Spy in the Metro Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu Submit Status Description Secret agent Maria was sent to Algorithms City to carry out an es

hdu3555---Bomb(数位dp,水)

Problem Description The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49&quo

hdu1520Anniversary party 树形dp水题

/* dp[i][0]表示第i个人不去的时候能得到的最大值 dp[i][1]表示第i个人去的时候得到的最大值 状态转移方程: dp[i][0]+=max(dp[next][0],dp[next][1]) dp[i][1]+=dp[next][0] 其中next为其子节点 */ #include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std;

合并石子 区间dp水题

合并石子 链接: nyoj 737 描述: 有N堆石子排成一排,每堆石子有一定的数量.现要将N堆石子并成为一堆.合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆.求出总的代价最小值. tags:最基本的区间dp,这题范围小,如果n大一些,还是要加个平行四边行优化. #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring&g

poj 1276 Cash Machine(dp 水题)

Language: Default Cash Machine Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 27799   Accepted: 9913 Description A Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate @ bills for a requested c

hdu4405Aeroplane chess 概率dp水题

//从0到n有n+1个格子 //对于格子i,掷一次骰子的数为x.那么能够从位置i到位置i+x //格子之间有连线,假设格子a和b有连线,那么从a到b不用掷骰子 //求从0到n的骰子掷的次数的期望 //dp[i] = 1/6*segma(dp[k]) + 1 (i<=k<=i+6) #include<cstdio> #include<iostream> #include<cstring> using namespace std ; const int maxn