题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1735
题目给出一张01图，1代表的是有字，0代表的是空格或者是被涂去的字。一共有m个段落，每个段落都是开头空两行，问最少有多少个字被涂去。
想要的到最少的被涂去的字必须保证每个段落之后的字尽量少。由此想到应该用贪心的策略。可以对开头空至少两个的行进行标记，那么他的上一行就有可能是一个段落的结尾行。如果要统计行内的0的个数的话就会十分复杂，可以换个角度思考，将格子总数-为1的位置的个数-段落开头格子数-最后一段末位连续0个数-（m-1）个末位最多0的段落的末位最多0的个数=被涂去的字数。这样就能统计每一段中的0的数量。减去最后一行的连续零可以理解为最后一行之后零的位置没有写字，这样总的被涂的字数才能最小。减去m-1个末位最多0的段落是因为第一行是第一段的开始。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x7ffffff 20 inline int read(){ 21 int ans=0,w=1; 22 char ch=getchar(); 23 while(!isdigit(ch)){if(ch==‘-‘)w=-1;ch=getchar();} 24 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-‘0‘,ch=getchar(); 25 return ans*w; 26 } 27 int n,m,t; 28 const int maxn=1e4+10; 29 int Map[maxn][105]; 30 int a[maxn]; 31 bool cmp(int a,int b){return a>b;} 32 int main() 33 { 34 //freopen("input.txt","r",stdin); 35 //freopen("output.txt","w",stdout); 36 while(~scanf("%d%d%d",&n,&m,&t)) 37 { 38 int tot=n*m; 39 mem(a,0); 40 f(i,0,n-1) 41 { 42 f(j,0,m-1) 43 { 44 scanf("%d",&Map[i][j]); 45 if(Map[i][j]==1)tot--;//每一行中的1不算在涂过的字数之内 46 } 47 } 48 int len=0; 49 int c=m-1; 50 while(Map[n-1][c]==0)tot--,c--;//处理出最后一行的末位0 51 f(i,1,n-1)//从第一段开始 52 { 53 int k=0; 54 if(Map[i][0]==0&&Map[i][1]==0)//开头两个字符为0，说明上一段可能是段尾 55 { 56 c=m-1; 57 while(Map[i-1][c]==0)c--,k++; 58 a[len++]=k+2;//段前两个空位加上段后的0 59 } 60 } 61 sort(a,a+len,cmp); 62 f(i,0,t-2)tot-=a[i];//选择t-1个段尾 63 tot-=2;//第一行开头的两个空位 64 pf("%d\n",tot); 65 } 66 }
原文：https://www.cnblogs.com/randy-lo/p/12621217.html