bzoj 1810: [Ioi2005]gar

.

题意：一个花园里有n朵花，用两个矩形不相交地框起两部分，使每个矩形内都有k朵花，并最小化周长。
题解：暴力处理出每一行往上和往下最小的周长，每一列往左和往右最小的周长。最后横竖扫一遍就好了。
代码：

#include<bits/stdc++.h>
#define pa pair<int,int>
using namespace std;

int l,w,n,K,sum[300][300],ans=1<<30,s1[300],s2[300],s3[300],s4[300];
pa a[5010];

int get(int x1,int y1,int x2,int y2)
{
    if(x1>x2)
    swap(x1,x2);
    if(y1>y2)
    swap(y1,y2);
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
int main()
{
    memset(s1,63,sizeof(s1));
    memset(s2,63,sizeof(s2));
    memset(s3,63,sizeof(s3));
    memset(s4,63,sizeof(s4));
    scanf("%d%d%d%d",&l,&w,&n,&K);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&a[i].first,&a[i].second);
        sum[a[i].first][a[i].second]++;
    }/*
    for(int i=1;i<=l;i++)
    {
        for(int j=1;j<=w;j++)
        printf("%d ",sum[i][j]);
        puts("");
    }
    puts("");*/
    for(int i=1;i<=l;i++)
    for(int j=1;j<=w;j++)
    {
        sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    }
    for(int i=1;i<=l;i++)
    for(int j=i;j<=l;j++)
    {
        for(int k=1,l=1;k<=w;k++)
        {
            while(l<k&&get(i,l+1,j,k)>=K)
            l++;
//            printf("%d %d %d %d %d\n",i,l,j,k,get(i,l,j,k));
            if(get(i,l,j,k)==K)
            {
                s1[j]=min(s1[j],(j-i+1+k-l+1)<<1);
                s2[i]=min(s2[i],(j-i+1+k-l+1)<<1);
            }
        }
    }
    for(int i=2;i<=l;i++)
    s1[i]=min(s1[i],s1[i-1]);
    for(int i=l-1;i>0;i--)
    s2[i]=min(s2[i],s2[i+1]);
    for(int i=1;i<=w;i++)
    for(int j=i;j<=w;j++)
    {
        for(int k=1,o=1;k<=l;k++)
        {
            while(o<k&&get(o+1,i,k,j)>=K)
            o++;
            if(get(o,i,k,j)==K)
            {
                s3[j]=min(s3[j],(j-i+1+k-o+1)<<1);
                s4[i]=min(s4[i],(j-i+1+k-o+1)<<1);
            }
        }
    }
    for(int i=2;i<=w;i++)
    s3[i]=min(s3[i],s3[i-1]);
    for(int i=w-1;i>0;i--)
    s4[i]=min(s4[i],s4[i+1]);/*
    for(int i=1;i<=l;i++)
    printf("%d %d\n",s1[i],s2[i]);
    puts("");
    for(int i=1;i<=w;i++)
    printf("%d %d\n",s3[i],s4[i]);*/
    for(int i=1;i<l;i++)
    {
        ans=min(ans,s1[i]+s2[i+1]);
    }
    for(int i=1;i<w;i++)
    {
        ans=min(ans,s3[i]+s4[i+1]);
    }
    if(ans==(1<<30))
    printf("NO");
    else
    printf("%d",ans);
}