Tag Archive: DP

URAL 1238. Folding

1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1238 1238. Folding Time limit: 1.0 second Memory limit: 64 MB Bill is trying to compactly represent sequences of capital alphabetic characters fr…
Read more

最大图样问题

  在最大正方形问题一篇中介绍了寻找最大正方形的方法,同样的方法稍加变化,即可用于寻找最大图样。 0. 问题描述   有M*N个正方形格子,其中一些格子涂成了蓝色,如图1中左图所示。求蓝色格子所能构成的最大十字的高度。图1中左图蓝色格子所能构成的最大十字高度为5,标记为深蓝色,如图1中右图。 1. 思路   十字不同于正方形,难以将寻找大十字的问题分解为寻找小十字的问题,那么考虑将十字拆分成为更加…
Read more

最大正方形问题

0. 问题描述   有M*N个正方形格子,其中一些格子涂成了蓝色,如图1所示。求蓝色格子所能构成的最大正方形边长。图1中蓝色格子所能构成的最大正方形边长为3。 1. 预处理   使用g[i][j]表示以第i行第j列的格子为右下角,所能构成的最大正方形的边长。对g[i][j]进行初始化: 如果格子为白色,令g[i][j] = 0; 如果格子为蓝色,令g[i][j] = 1。   得到结果如图2。注意…
Read more

POJ 3356. AGTC

1. 题目 http://poj.org/problem?id=3356 AGTC Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10970 Accepted: 4217 Description Let x and y be two strings over some finite alphabet A. We would l…
Read more