hdu1937 Finding Seats（尺取）

题意：

给定n*m的图，和一个整数k，
图由’X‘和’.‘组成，现在要求你找到一个面积最小的子矩阵，满足子矩阵中的’.'不少于k个。
输出最小面积。

数据范围：n,m<=300，k<=n*m

解法：

考虑1*m的矩阵，如果要求找到一个最小的子矩阵，满足不少于k个，
可以直接尺取。

那么n*m怎么做呢，枚举行i和行j，将[i,j]行合并为一行，每一列是[i,j]列的权值和。
然后就变成上面的情况了，进行尺取即可。

枚举i,j的复杂度为O(n²)，尺取O(n)，总复杂度O(n³)

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define PI pair<int,int>
const int maxm=305;
char s[maxm][maxm];
int sum[maxm][maxm];
int temp[maxm];
int a[maxm];
int n,m,k;
signed main(){
    ios::sync_with_stdio(0);while(cin>>n>>m>>k){
    if(!(n+m+k))break;for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    cin>>s[i][j];}}for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+(s[i][j]=='.');}}int ans=n*m;for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
    for(int t=1;t<=m;t++){
    temp[t]=sum[j][t]-sum[i-1][t];}int p=1;for(int t=1;t<=m;t++){
    while(temp[t]-temp[p-1]>=k){
    ans=min(ans,(j-i+1)*(t-p+1));p++;}}}}cout<<ans<<endl;}return 0;
}