R - Finding Seats HDU - 1937 (尺取法)(二维前缀和)

A group of K friends is going to see a movie. However, they are too late to get good tickets, so they are looking for a good way to sit all nearby. Since they are all science students, they decided to come up with an optimization problem instead of going on with informal arguments to decide which tickets to buy.

The movie theater has R rows of C seats each, and they can see a map with the currently available seats marked. They decided that seating close to each other is all that matters, even if that means seating in the front row where the screen is so big it’s impossible to see it all at once. In order to have a formal criteria, they thought they would buy seats in order to minimize the extension of their group.

The extension is defined as the area of the smallest rectangle with sides parallel to the seats that contains all bought seats. The area of a rectangle is the number of seats contained in it.

They’ve taken out a laptop and pointed at you to help them find those desired seats.
Input
Each test case will consist on several lines. The first line will contain three positive integers R, C and K as explained above (1 <= R,C <= 300, 1 <= K <= R × C). The next R lines will contain exactly C characters each. The j-th character of the i-th line will be ‘X’ if the j-th seat on the i-th row is taken or ‘.’ if it is available. There will always be at least K available seats in total.
Input is terminated with R = C = K = 0.
Output
For each test case, output a single line containing the minimum extension the group can have.
Sample Input
3 5 5
…XX
.X.XX
XX…
5 6 6
…X.X.
.XXX…
.XX.X.
.XXX.X
.XX.XX
0 0 0
Sample Output
6
9

被这道题安排了,套尺取法模板的时候一定要理解算法,才能在各种情况下调整。

#include<iostream>
#include<stdio.h>
#include<stack>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
int n;
int a[400][400];
int sum[400][400];

int main(){
    int r,c,k;
    while(~scanf("%d%d%d",&r,&c,&k)){
        int ans=r*c+1;
        if(r==0&&c==0&&k==0) break;
        for(int i=1;i<=r;i++){
          getchar();
            for(int j=1;j<=c;j++){
                char tem;
                scanf("%c",&tem);
                if(tem=='.')a[i][j]=1;
                else a[i][j]=0;
                a[i][j]+=(a[i-1][j]+a[i][j-1]-a[i-1][j-1]);
 // cout<<a[i][j];
            }
 // cout<<endl;

        }
        for(int i = 1;i <= r;i ++) {
            for(int j = 1;j <= r;j ++) {
                int left = 1,right = 1;
                while(right <= c && left <= right) {
                    if(get(i,j,left,right)< k) right ++;
                    else {
                        ans = min(ans,(j - i + 1) * (right - left + 1));
                        left ++;
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
}

全部评论

相关推荐

点赞 评论 收藏
分享
牛客83700679...:简历抄别人的,然后再投,有反馈就是简历不行,没反馈就是学历不行,多投多改只要技术不差机会总会有的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务