HOJ 2133&POJ 2964 Tourist(动态规划)

Tourist Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1503 Accepted: 617 Description

A lazy tourist wants to visit as many interesting locations in a city as possible without going one step further than necessary. Starting from his hotel, located in the north-west corner of city, he intends to take a walk to the south-east corner of the city and then walk back. When walking to the south-east corner, he will only walk east or south, and when walking back to the north-west corner, he will only walk north or west. After studying the city map he realizes that the task is not so simple because some areas are blocked. Therefore he has kindly asked you to write a program to solve his problem.

Given the city map (a 2D grid) where the interesting locations and blocked areas are marked, determine the maximum number of interesting locations he can visit. Locations visited twice are only counted once. Input

The first line in the input contains the number of test cases (at most 20). Then follow the cases. Each case starts with a line containing two integers, W and H (2 ≤ W, H ≤ 100), the width and the height of the city map. Then follow H lines, each containing a string with W characters with the following meaning:

‘.’ Walkable area ‘*’ Interesting location (also walkable area) ‘#’ Blocked area

You may assume that the upper-left corner (start and end point) and lower-right corner (turning point) are walkable, and that a walkable path of length H + W - 2 exists between them. Output

For each test case, output a line containing a single integer: the maximum number of interesting locations the lazy tourist can visit. Sample Input

2 9 7 *…….. …..**#. ..*…# ..####*#. ..#.*#. …#**… *…….. 5 5 ... *###. ..* .###* ... Sample Output

7 8

经常写这种在一个矩阵里从左上角走到右下角,只能向下和向右走,这种是一个水DP。这道题目就是这类题目的升级类型。就是走到右下角还要返回左上角,以前走过的景点返回时走过都不算。我一开始天真的以为先求左上角到右下角的DP,再把图变一下,求右下角到左上角的DP,这样第二个样例就过不了。所以就要换一种方式,去的和来的不能分开DP,只能将他们和在一起才能得到正确的解。看了题解,状态是DP[i][j][k],表示到第i条斜线,去的路的横坐标是j,来的路的横坐标是k。还有的解法是i是第几步。 可以看出,如果一道题目的解法是动态规划,那么一定有其相应的状态转移方程,不能局限于题目的给的条件,

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>

using namespace std;
int dp[205][105][105];
int n,m;
int t;
char a[105][105];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        for(int i=0;i<n;i++)
            scanf("%s",a[i]);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=m+n-1;i++)
        {
            for(int j=0;j<n;j++)
            {
                for(int k=0;k<n;k++)
                {
                    int y1=(i-1)-j;
                    if(y1<0)
                        continue;
                    if(y1>=m)
                        continue;
                    int y2=(i-1)-k;
                    if(y2<0)
                        continue;
                    if(y2>=m)
                        continue;
                    if(a[j][y1]=='#'||a[k][y2]=='#')
                    {dp[i][j][k]=0;continue;}
                    int ans=-2;
                    if(j-1>=0)
                        ans=max(ans,dp[i-1][j-1][k]);
                    if(k-1>=0)
                        ans=max(ans,dp[i-1][j][k-1]);
                    if(k-1>=0&&j-1>=0)
                        ans=max(ans,dp[i-1][j-1][k-1]);
                    ans=max(ans,dp[i-1][j][k]);
                    if(ans==-1)
                    {dp[i][j][k]=-1;continue;}
                    else
                        dp[i][j][k]=ans;
                    if(a[j][y1]=='*'&&y1!=y2)
                        dp[i][j][k]++;
                    if(a[k][y2]=='*'&&y1!=y2)
                        dp[i][j][k]++;
                    if(a[k][y2]=='*'&&a[j][y1]=='*'&&y1==y2)
                        dp[i][j][k]++;
                }
            }
        }
        printf("%d\n",dp[m+n-1][n-1][n-1]);


    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 2080 夹角有多大II

夹角有多大II Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

278100
来自专栏数据结构与算法

2-SAT速成

本文只做总结性说明 2-SAT 2-SAT是k-SAT问题的一种,k-SAT问题在k>=3时已经被证明是NP完全问题 2-SAT问题定义比较简单 有n个布尔变量...

28860
来自专栏bboysoul

1475: C语言实验题――一元二次方程 II

描述:求一元二次方程ax2+bx+c=0的解。a,b,c为任意实数。 输入:输入数据有一行,包括a b c的值 输出:按以下格式输出方程的根x1和x2。x1...

12930
来自专栏HansBug's Lab

4063: [Cerc2012]Darts

4063: [Cerc2012]Darts Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 85  Solve...

358110
来自专栏数据结构与算法

欧拉函数详解

欧拉函数 我们用 表示欧拉函数 定义: 表示对于整数n,小于等于n中与n互质的数的个数 性质 1. 为积性函数 证明: 此处证明需要用到下面计算方法1中的...

32340
来自专栏数据魔术师

运筹学教学 | 十分钟教你求解分配问题(assignment problem)

biu~ biu~ biu~ 我们的运筹学教学推文又出新文拉 还是熟悉的配方,熟悉的味道 今天向大家推出的是 运筹学教学--第六弹 分配问题(Assignmen...

1.5K80
来自专栏小鹏的专栏

tensorflow使用BN—Batch Normalization

注意:不要随便加BN,有些问题加了后会导致loss变大。 上一篇是 Batch Normalization的原理介绍,看一下tf的实现,加到卷积后面和全连接层...

1.1K70
来自专栏小樱的经验随笔

BZOJ 1800: [Ahoi2009]fly 飞行棋【思维题,n^4大暴力】

1800: [Ahoi2009]fly 飞行棋 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 1689  So...

30480
来自专栏ml

hdu----(1466)计算直线的交点数(dp)

计算直线的交点数 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (...

40970
来自专栏chenjx85的技术专栏

leetcode-458-Poor Pigs

18840

扫码关注云+社区

领取腾讯云代金券