codeforces 496 C Removing Columns (构造)

题目链接

题意:给一个n*m的由小写字母组成的table.要求从上往下每一行字典序不严格递增。问最少删除几列才能满足。

思路:一开始想的是用一个left数组维护每次删除后某一列左边是哪一列,目的是为了下次的判断。

再想了下,发现没必要。我们只需要知道,两行之间的关系是否确定就好了。over[i][j]为真表示第i行和第j行的胜负已分,对于胜负已分的行,大小无所谓。

对于胜负未分的行,如果table[i][j]>table[i+1][j],就必须要删掉这一列了。。。。

需要注意的是,某一列最多删一次,记得打上标记。

以及ove标记的时候,要在最后确定这一列没有被删以后再标记。。。用一个set存下可能的胜负已分的行的下标即可。

1A

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz