[HDU3262 Seat taking up is tough]

[關鍵字]：枚舉 模拟

[題目大意]：n*m的矩陣，每個矩陣有一個舒适值，給出每個學生進入教室的順序和它需要占的位子數，隻能占連續的一個橫條最左邊的是他的位置，每次都占他的位置舒适度最大。如果不夠則隻占它自己的位置，輸出他所在的位置的坐标，如果一個位置都不剩就輸出-1。

//========================================================================================================

[分析]：枚舉每一坐标作為自己的位置然後判斷其後是否夠，如果夠就和目前最優指比較。如果都查完都不夠就找到全圖中可用的最大的舒适度給自己，如果還沒有那就輸出-1.注意的是每個學生到達的時間不一定是按順序給出的，是以要先排序。

[代碼]：

View Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=33;

struct rec
{
int x,y,d;
}ans[MAXN*2];
struct node
{
int h,m,dat,num;
}a[MAXN*2];
int n,m,k;
int map[MAXN][MAXN];
bool b[MAXN][MAXN];

bool cmp(node a,node b)
{
if (a.h<b.h || (a.h==b.h && a.m<b.m)) return 1; else return 0;
}

bool Init()
{
    scanf("%d%d%d",&n,&m,&k);
if (!n && !m && !k) return 0;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
            scanf("%d",&map[i][j]);
for (int i=1;i<=k;++i)
        scanf("%d:%d %d",&a[i].h,&a[i].m,&a[i].dat),a[i].num=i;
    sort(a+1,a+k+1,cmp);
//for (int i=1;i<=k;++i) printf("%d %d %d %d\n",a[i].num,a[i].h,a[i].m,a[i].dat);
    return 1;
}

bool Cleck(int x,int y,int z)
{
for (int i=y;i<=y+z-1;++i)
if (b[x][i]) return 0;
return 1;
}

bool GF(int h)
{
    rec Max;
    Max.x=Max.y=Max.d=0;
for (int i=1;i<=n;++i)
for (int j=1;j<=m-a[h].dat+1;++j)
if (Cleck(i,j,a[h].dat))
if (map[i][j]>Max.d) 
                    Max.x=i,Max.y=j,Max.d=map[i][j];
if (Max.x && Max.y) 
    {
        ans[a[h].num]=Max;
for (int i=Max.y;i<=Max.y+a[h].dat-1;++i) b[Max.x][i]=1;
return 1;
    }
return 0;
}

bool GM(int h)
{
    rec Max;
    Max.x=Max.y=Max.d=0;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (!b[i][j] && Max.d<map[i][j]) Max.x=i,Max.y=j,Max.d=map[i][j];
if (Max.x && Max.y) 
    {
        ans[a[h].num]=Max,b[Max.x][Max.y]=1;
return 1;
    }
return 0;
}

void Solve()
{
    memset(ans,0,sizeof(ans));
    memset(b,0,sizeof(b));
//printf("%d %d\n",n,m);
    for (int i=1;i<=k;++i)
    {
if (GF(i)) continue;
if (GM(i)) continue;
        ans[a[i].num].d=-1;
    }
for (int i=1;i<=k;++i)
if (ans[i].d!=-1) printf("%d %d\n",ans[i].x,ans[i].y); else printf("-1\n");
}

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
while (Init()) Solve();
return 0;
}      

轉載于:https://www.cnblogs.com/procedure2012/archive/2012/03/13/2393356.html