Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给一个n*m的由小写字母组成的table.要求从上往下每一行字典序不严格递增。问最少删除几列才能满足。
思路：一开始想的是用一个left数组维护每次删除后某一列左边是哪一列，目的是为了下次的判断。
再想了下，发现没必要。我们只需要知道，两行之间的关系是否确定就好了。over[i][j]为真表示第i行和第j行的胜负已分，对于胜负已分的行，大小无所谓。
对于胜负未分的行，如果table[i][j]>table[i+1][j]，就必须要删掉这一列了。。。。
需要注意的是，某一列最多删一次，记得打上标记。
以及ove标记的时候，要在最后确定这一列没有被删以后再标记。。。用一个set存下可能的胜负已分的行的下标即可。
1A
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年10月04日 星期二 19时10分39秒
4File Name :code/cf/problem/496C.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <deque>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <bitset>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32const int N=105;
33char table[N][N];
34int n,m;
35bool mark[N];
36bool over[N][N];
37int left[N];
38int main()
39{
40 #ifndef ONLINE_JUDGE
41 freopen("code/in.txt","r",stdin);
42 #endif
43 cin>>n>>m;
44 ms(mark,false);
45 ms(over,false);
46 for ( int i = 0 ; i < n ; i++) scanf("%s",table[i]);
47 int cnt = 0 ;
48 for ( int j = 0 ; j < m ; j++)
49 {
50 set< int >se;
51 bool del = false;
52 for ( int i = 0 ; i < n-1 ; i++)
53 {
54 if (table[i][j]<table[i+1][j])
55 {
56 se.insert(i);
57 }
58 else if (table[i][j]>table[i+1][j]&&!over[i][i+1]&&!mark[j])
59 {
60 cnt++;
61 del = true;
62 mark[j] = true;
63 // cout<<"delete:"<<j<<endl;
64 }
65 }
66 if (!del)
67 {
68 for ( auto it = se.begin (); it!=se.end(); it++)
69 {
70 over[*it][*it+1] = true;
71 }
72 }
73 }
74 printf("%d\n",cnt);
75 #ifndef ONLINE_JUDGE
76 fclose(stdin);
77 #endif
78 return 0;
79}