标签: 普通DP

「HDU 6416」Rikka with Seam

Seam carving is a novel algorithm for resizing images while maintaining as much information as possible from the source image.

Now, Rikka is going to use seam carving method to deal with an n×m black and white picture. We can abstract this picture into an n×m 01 matrix A.

「CodeForces 1198D」 Rectangle Painting 1

There is a square grid of size n×nn \times n. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs max(h,w)\max(h, w) to color a rectangle of size h×wh \times w. You are to make all cells white for minimum total cost.

「SCOI2010」股票交易

最近 lxhgww 又迷上了投资股票,通过一段时间的观察和学习,他总结出了股票行情的一些规律。

通过一段时间的观察,lxhgww 预测到了未来 T 天内某只股票的走势,第 i 天的股票买入价为每股 AP_i,第 ii 天的股票卖出价为每股 BP_i(数据保证对于每个 i,都有 APiBPiAP_i \geq BP_i,但是每天不能无限制地交易,于是股票交易所规定第 i 天的一次买入至多只能购买 AS_i股,一次卖出至多只能卖出 BS_i股。

另外,股票交易所还制定了两个规定。为了避免大家疯狂交易,股票交易所规定在两次交易(某一天的买入或者卖出均算是一次交易)之间,至少要间隔 WW 天,也就是说如果在第 ii 天发生了交易,那么从第 i+1 天到第 i+W 天,均不能发生交易。同时,为了避免垄断,股票交易所还规定在任何时间,一个人的手里的股票数不能超过 MaxP。

在第 1 天之前,lxhgww 手里有一大笔钱(可以认为钱的数目无限),但是没有任何股票,当然,T 天以后,lxhgww 想要赚到最多的钱,聪明的程序员们,你们能帮助他吗?

「CodeForces 1247E」Rock Is Push

You are at the top left cell (1,1) of an 𝑛×𝑚 labyrinth. Your goal is to get to the bottom right cell (𝑛,𝑚). You can only move right or down, one cell per step. Moving right from a cell (𝑥,𝑦) takes you to the cell (𝑥,𝑦+1), while moving down takes you to the cell (𝑥+1,𝑦).

「Comet OJ - Contest #11」usiness

一张笑盈盈的脸挡住了替罪羊树的去路,那不怀好意的笑容使困倦的银发少女皱了皱眉。「 sgt ,你有多长时间没打理过那些可怜的节点了?恕我直言,你的本体看上去可不是一般的斜。」

「只是我今天的 αα\alphaα 设得比较大…」替罪羊树辩解的同时,心虚地偏了下身子试图遮住背后长歪二叉树的虚影。

「POJ 1417」True Liars

After having drifted about in a small boat for a couple of days, Akira Crusoe Maeda was finally cast ashore on a foggy island. Though he was exhausted and despaired, he was still fortunate to remember a legend of the foggy island, which he had heard from patriarchs in his childhood. This must be the island in the legend. In the legend, two tribes have inhabited the island, one is divine and the other is devilish, once members of the divine tribe bless you, your future is bright and promising, and your soul will eventually go to Heaven, in contrast, once members of the devilish tribe curse you, your future is bleak and hopeless, and your soul will eventually fall down to Hell.

「CF1012C」 Hills

Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city construction.

From the window in your room, you see the sequence of n hills, where i-th of them has height ai. The Innopolis administration wants to build some houses on the hills. However, for the sake of city appearance, a house can be only built on the hill, which is strictly higher than neighbouring hills (if they are present). For example, if the sequence of heights is 5, 4, 6, 2, then houses could be built on hills with heights 5 and 6 only.

「CF 1152D」 Neko and Aki's Prank

Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...

It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a trie of all correct bracket sequences of length 2n.