【NOIP 2010】水を引いて城DFS+欲張り

7223 ワード

欲が深い ==基礎アルゴリズム===

問題は図があって、添付しないで、面倒ですね......
http://codevs.cn/problem/1066/
私の考えは、第1列の各点に対してdfsを1回行い、制御可能な区間(遡及更新)を得ることです.
制御された区間が1つでなければ(すなわち中間に割り込みがある)、必ずすべてをカバーすることはできないことが証明されている.
1回ごとにdfsを注文すると、時間の複雑さが高すぎて、爆発する可能性があります.記憶化すればいいです.そうすれば、時間の複雑さも耐えられます.これは私が欠点を書きました.長い間調整しました.とっくに知っていたら、dfsを殴らないでください.bfsは実は書きやすいです.
dfsはmaps[i][j]を設定して2つの値:という点が制御する区間の左右の端点を保存し、検索した点を検索したらmaps更新をそのまま利用すればよい.
次はセグメントオーバーライドです.セグメントの山をあげて、できるだけ多くのセグメントを取り除いて、残りのセグメントが区間全体をオーバーライドできるようにします.
それから私は黄先輩の標高(IQが低い...)を見て、たぶんそうです.
まず、左端の昇順を第1キーワード、右端の昇順を第2キーワードとしてソートします.
2つの変数を設定します:nowとtoは、現在の最大がnowビットに拡張され、次の区間が最大でtoビットに拡張されることを示します.now+1>=l[i].l(現在の区間がnowに接続可能であり、中間に隙間がないことを示す)であれば、上記の関係を満たさないまでtoを更新し、すなわち最後にtoを更新する区間を選択する(実際にはどの区間なのかは気にしない).最後に忘れないでください.nowが最右端に届かない場合はans++;
コード:

#include
#include
#include
#include
using namespace std;
const int INF=233333333;
const int SIZE=1010;
int num[600][600];
int n,m;

const int dx[]={0,-1,0,1,0};
const int dy[]={0,0,1,0,-1};

struct qujian{
    int l,r;
}l[SIZE],maps[600][600];

bool vis[600][600];
void dfs(int x,int y,int sy)
{
    if(x==n)
    {
        maps[x][y].l=y;maps[x][y].r=y;
    }
    vis[x][y]=1;
    for(int i=1;i<=4;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>0&&nx<=n&&ny>0&&ny<=m&&num[nx][ny]if(vis[nx][ny]) 
            {
                maps[x][y].l=min(maps[x][y].l,maps[nx][ny].l);
                maps[x][y].r=max(maps[x][y].r,maps[nx][ny].r);
            }            
            else 
            {
                maps[nx][ny].l=INF; maps[nx][ny].r=0;
                dfs(nx,ny,sy);
                vis[nx][ny]=1;
                maps[x][y].l=min(maps[x][y].l,maps[nx][ny].l);
                maps[x][y].r=max(maps[x][y].r,maps[nx][ny].r);
            }
        }
    }
}



bool cmp(qujian a,qujian b)
{
    if(a.l!=b.l)   return a.lreturn a.rint main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&num[i][j]); 
        }
    }

    for(int i=1;i<=m;i++)
    {
        if(!vis[1][i]&&num[1][i]>=num[1][i+1])
        {
            maps[1][i].l=INF; maps[1][i].r=0;
            dfs(1,i,i);
        }
    }
    int tot=0;
    for(int i=1;i<=m;i++)
    {
        if(!vis[n][i]) tot++;
    }

    if(tot)
    {
        printf("0
%d",tot);
        return 0;
    }

    int len=0;
    for(int i=1;i<=m;i++) 
        if(maps[1][i].r)    
            l[++len].l=maps[1][i].l,l[len].r=maps[1][i].r;

    sort(l+1,l+1+len,cmp);


    int now=0,ans=0;
    for(int i=1,to=0;i<=len;i++)
    {
        if(now+1>=l[i].l) to=max(to,l[i].r);
        else now=to,to=max(to,l[i].r),ans++;
    }
    if(now!=m) ans++;
    printf("1
%d",ans);
    return 0;
} 
/*
3 6
8 4 5 6 4 4 
7 3 4 3 3 3
3 2 2 1 1 2

2 5
9 1 5 4 3
8 7 6 1 2

g++ codevs1066.cpp -o codevs1066.exe -Wall

*/

css 3ピクチャサスペンション効果

OTP Design Principles: Gen_Server Behaviour