文档章节

sgu 168

m2012
 m2012
发布于 2012/05/06 11:00
字数 487
阅读 101
收藏 0
这题本来以为很容易可以过,结果在test 3 WA了好多次
这题有个很容易想漏的地方。
首先,画个图,搞清楚B[i][j]的含义。
一开始,会想到转移方程应该就是
B[i][j] = min { A[i][j], B[i+1][j], B[i-1][j+1] }
可是, B[i+1][j] 和 B[i-1][j+1]都有可能超界
譬如说,在一个A[1..3][1..3]的矩阵里面,B[1][2]需要用到B[2][2] 和 B[0][3],这个B[0][3]是不存在的,但是并不能忽略掉,我WA on test 3的原因就在于,我先判断这个要用到的东西是不是超界,如果超界就忽略掉。
既然B[0][3]不存在,但是又不能忽略掉,那怎么办?很简单,我们可以再添加一个 B[i][j+1]!

正确的转移方程应该是:

B[i][j] = min { A[i][j], B[i+1][j], B[i-1][j+1], B[i][j+1] }

 

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;


template <class VVType, class T>
void make2DVector(VVType &a, int d, int f, const T &initValue) {
    int i, j;
    a.resize(d);
    for (i = 0; i < d; ++i) {
        a[i].resize(f);
        for (j = 0; j < f; ++j) a[i][j] = initValue;
    }
}


int N, M;
int lastRow, lastCol;
vector< vector<int> > A, B;


inline bool isInside(int i , int j) {
    return 1 <= i && i <= lastRow && 1 <= j && j <= lastCol;
}

void run() {
    int i, j;
    for (j = lastCol; j >= 1; --j) {
        for (i = lastRow; i >= 1; --i) {
            B[i][j] = A[i][j];
            if (isInside(i-1, j+1)) B[i][j] = min(B[i][j], B[i-1][j+1]);
            if (isInside(i, j+1)) B[i][j] = min(B[i][j], B[i][j+1]);
            if (isInside(i+1, j)) B[i][j] = min(B[i][j], B[i+1][j]);
        }
    }
}

void output() {
    int i, j;
    for (i = 1; i <= N; ++i) {
        for (j = 1; j <= M; ++j) {
            if (j == 1) printf("%d", B[i][j]);
            else printf(" %d", B[i][j]);
        }
        printf("\n");
    }
}

void input() {
    scanf("%d %d", &N, &M);
    lastRow = N;
    lastCol = M;
    make2DVector(A, N + 1, M + 1, 0);
    make2DVector(B, N + 1, M + 1, 0);
    int i, j;
    for (i = 1; i <= N; ++i) {
        for (j = 1; j <= M; ++j) {
            int a;
            scanf("%d", &a);
            A[i][j] = a;
        }
    }
}


int main() {
    input();
    run();
    output();
    return 0;
}

© 著作权归作者所有

共有 人打赏支持
上一篇: sgu 179
下一篇: sgu 143
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
网络流建模汇总结

因为网上Dinic模板大多不规范或者可以被卡,所以先贴出一份跑得比较快的Dinic模板(主要快在maxflow()里面,可以仔细体会)。 (以下题意请自行百度) 1.最优分配 poj1149 应该是很裸的题了。...

qq_35649707
2017/08/04
0
0
SGU题目列表(按照AC人数排序)

15509 100 A+B 05909 102 Coprimes 05424 105 Div 3 05024 123 The sum 03552 115 Calendar 03365 135 Drawing Lines 03235 184 Patties 03103 107 987654321 problem 03019 113 Nearly prim......

m2012
2012/04/29
0
0
SGU209 Areas 【平面图】

题目大意: 给出n条直线,问直线围成的所有闭合区域的个数及面积,按面积大小升序输出。(n<=80) 解题思路: ①我们需要求出两两直线的交点; ②再对每条直线上的交点排序,来求出所有分割成...

cdsszjj
2017/12/25
0
0
网络爬虫引擎--simspider

simspider - 网络爬虫引擎 1.简介 simspider是一个轻巧的跨平台的网络爬虫引擎,它提供了一组C函数接口用于快速构建你自己的网络爬虫应用,同时也提供了一个可执行的爬虫程序用于演示函数接口...

calvinwilliams
2015/02/09
4.7K
0
RHEL6 搭建 keepalived + lvs/DR 集群

搭建 keepalived + lvs/DR 集群 使用Keepalived为LVS调度器提供高可用功能,防止调度器单点故障,为用户提供Web服务: LVS1调度器真实IP地址为192.168.4.50 LVS2调度器真实IP地址为192.168.4...

Xuenqlve
2018/01/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot项目如何访问jsp页面

1.添加pom依赖 首先在原来的pom文件基础上加上这两个配置 如果想学习Java工程化、高性能及分布式、深入浅出。微服务、Spring,MyBatis,Netty源码分析的朋友可以加我的Java高级交流:7877071...

编程SHA
23分钟前
3
0
nginx反向代理配置去除前缀

使用nginx做反向代理的时候,可以简单的直接把请求原封不动的转发给下一个服务。设置proxy_pass请求只会替换域名,如果要根据不同的url后缀来访问不同的服务,则需要通过如下方法: 方法一:...

架构师springboot
55分钟前
5
0
QianBill API 开发笔记

JWT

BeanHo
今天
5
0
Elasticsearch实战篇——Spring Boot整合ElasticSearch

当前Spring Boot很是流行,包括我自己,也是在用Spring Boot集成其他框架进行项目开发,所以这一节,我们一起来探讨Spring Boot整合ElasticSearch的问题。 本文主要讲以下内容: 第一部分,通...

JAVA_冯文议
今天
4
0
不错的linux下通用的java程序启动脚本

#!/bin/sh#该脚本为Linux下启动java程序的通用脚本。即可以作为开机自启动service脚本被调用,#也可以作为启动java程序的独立脚本来使用。##Author: tudaxia.com, Date: 2011/6/7...

sprouting
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部