USACO2005 JAN GOLD

时间：2010-10-14 来源：LitIce

Muddy Fields

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1735

------------------------------------------------------------------------------------

把行里面连在一起的坑连起来视为一个点，即一块横木板，编上序号，Sample则转化为：

1 0 2 0
0 3 3 3
4 4 4 0
0 0 5 0

把这些序号加入X集合，再按列做一次则为：

1 0 4 0
0 3 4 5
2 3 4 0
0 0 4 0

同样加入Y集合，一个坑只能被横着的或者被竖着的木板盖住，将原图的坑的也标上不同的序号，一共九个坑

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

图中的2号低洼处既可以拿横着的2号板，也可以拿竖着的4号板来覆盖，那么2号版和四号板之间就有一条边，表式低洼处。用最少的点把所有的边连起来，这样就是最小点覆盖。

-----------------------------------------------------------------------------------------

以上构图巧妙~转自：http://www.cppblog.com/abilitytao/archive/2009/10/21/99124.aspx

The Wedding Juicer

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1736

按照黑书上的做法：建立一个优先队列，将外围点入队。每次取出高度最小的点更新，

更新时如果遇到比自己低的就注入水到自己高度。接着把遇到的点加入优先队列。

Naptime

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1737

DP!f[i][j] 前i个时间段取j个时间段，但是第i个时间段不取。g[i][j] 前i个时间段取j个时间段，且第i个时间段取。

f[i][j]=max{f[i-1][j],g[i-1][j]}

g[i][j]=max{f[i-1][j-1],g[i-1][j-1]+a[i]}

初始均为0

用f[n][m]和g[n][m]更新ans

现在再考虑第可以循环~- -！再做一遍！

令g[1][1]=a[1];最后用g[n][m]更新ans

HYOJ1735_Muddy Fields

#include<iostream>
#include<cstdio>
#define N 501
using namespace std;
struct node{
            int y,next;
       };
node E[N*N];
int edg[N],map1[N][N],map2[N][N],cnt,cnt1,cnt2,n,m,match[N],ans;
char map[N][N];
bool vis[N];
void add_edge(int x,int y)
{
     ++cnt;E[cnt].y=y;E[cnt].next=edg[x];edg[x]=cnt;
 }
bool dfs(int u)
{
     for (int i=edg[u];i!=0;i=E[i].next)
     if (vis[E[i].y]==0)
     {
         vis[E[i].y]=1;
         if (match[E[i].y]==0 || dfs(match[E[i].y])) 
         {
                               match[E[i].y]=u;
                               return 1;
         }
     }
     return 0;
 }
int main()
{
    freopen("HYOJ1735.in","r",stdin);
    freopen("HYOj1735.out","w",stdout);
    scanf("%d%d\n",&n,&m);
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=m;++j)
            scanf("%c",&map[i][j]);
        scanf("\n");
    }
    
    cnt1=0;
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=m;++j)
        {
            if (j==1)
            {
                    if (map[i][j]=='*') map1[i][j]=++cnt1;
            }else
            {
                    if (map[i][j]=='*' && map[i][j-1]=='*')
                    {map1[i][j]=map1[i][j-1];continue;}
                    if (map[i][j]=='*') map1[i][j]=++cnt1;
                    
             }
        }
    }
    
    cnt2=0;
    for (int j=1;j<=m;++j)
    {
        for (int i=1;i<=n;++i)
        {
            if (i==1)
            {
                    if (map[i][j]=='*') map2[i][j]=++cnt2;
            }else
            {
                 if (map[i][j]=='*' && map[i-1][j]=='*')
                 {map2[i][j]=map2[i-1][j];continue;}
                 if (map[i][j]=='*') map2[i][j]=++cnt2;
             }
        }
    }
    cnt=0;


    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
        if (map[i][j]=='*')
        {
            add_edge(map1[i][j],map2[i][j]);
           // printf("%d %d\n",map1[i][j],map2[i][j]);
        }
  
    for (int i=1;i<=cnt1;++i)
    {
        for (int j=1;j<=cnt2;++j) vis[j]=0;
        if (dfs(i)) ++ans;
    } 
    printf("%d\n",ans);
    return 0;

}

HYOJ1736_The Wedding Juicer

#include<iostream>
#include<cstdio>
using namespace std;
#define N 301
struct node{
            int key,x,y;
       };    

node PQ[N*N+10];
bool vis[N][N];
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m,x,y,xx,yy,ans,cnt,t,pos,jj;
int map[N][N];
void swap(int x,int y)
{
     t=PQ[x].key;PQ[x].key=PQ[y].key;PQ[y].key=t;
     t=PQ[x].x;PQ[x].x=PQ[y].x;PQ[y].x=t;
     t=PQ[x].y;PQ[x].y=PQ[y].y;PQ[y].y=t;
 }
void PQ_add(int key,int x,int y)
{
     ++cnt;PQ[cnt].key=key;PQ[cnt].x=x;PQ[cnt].y=y;
     vis[x][y]=1;
     pos=cnt;
     while (pos>1)
     {
           if (PQ[pos/2].key>PQ[pos].key) swap(pos/2,pos); else break;
           pos/=2;
     }
 }
void calc(int h,int x,int y)
{
     for (int i=0;i<=3;++i)
     {
         xx=x+d[i][0];yy=y+d[i][1];
         if (xx>=1 && xx<=n && yy>=1 && yy<=m && vis[xx][yy]==0)
         {
                   if (h>map[xx][yy]) 
                   {
                                    ans+=(h-map[xx][yy]);
                                    map[xx][yy]=h;
                   }
                   PQ_add(map[xx][yy],xx,yy);
         }
     }
 }
int main()
{
    freopen("HYOJ1736.in","r",stdin);
    freopen("HYOJ1736.out","w",stdout);
    scanf("%d%d",&m,&n);
    for (int i=1;i<=n;++i)
    for (int j=1;j<=m;++j)
    {
        scanf("%d",&map[i][j]);
        if (i==1 || i==n || j==1 || j==m)
        {
                 PQ_add(map[i][j],i,j);
        }
    }

    while (cnt>0)
    {
          calc(PQ[1].key,PQ[1].x,PQ[1].y);
          swap(1,cnt);
          --cnt;
          pos=1;
          while (pos<=cnt)
          {
                jj=pos;
                if (pos*2<=cnt && PQ[pos*2].key<PQ[jj].key) jj=pos*2;
                if (pos*2+1<=cnt && PQ[pos*2+1].key<PQ[jj].key) jj=pos*2+1;
                if (jj==pos) break;
                swap(jj,pos);
                pos=jj;
          }

    }
    printf("%d",ans);
    return 0;
}

HYOJ1737_Naptime

#include<iostream>
#include<cstdio>
using namespace std;
#define N 3831

int n,m,ans;
int f[2][N],g[2][N],a[N];
int max(int a,int b)
{
    if (b>a) a=b; return a;
}
int main()
{
    freopen("HYOJ1737.in","r",stdin);
    freopen("HYOJ1737.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
        scanf("%d",&a[i]);

    for (int i=2;i<=n;++i)
    {
     for (int j=1;j<=m;++j)
     {
         if (j>i) break;
         f[1][j]=max(f[0][j],g[0][j]);
         if (j>1)
         g[1][j]=max(f[0][j-1],g[0][j-1]+a[i]);
     }
     for (int j=0;j<=m;++j) g[0][j]=g[1][j],g[1][j]=0,f[0][j]=f[1][j],f[1][j]=0;
    }
     
    ans=max(f[0][m],g[0][m]);//printf("%d",ans);
    for (int j=0;j<=m;++j) f[0][j]=0,g[0][j]=0;
    
    g[0][1]=a[1];
    for (int i=2;i<=n;++i)
    {
     for (int j=1;j<=m;++j)
     {
         if (j>i) break;
         f[1][j]=max(f[0][j],g[0][j]);
         if (j>1)
         g[1][j]=max(f[0][j-1],g[0][j-1]+a[i]);
     }
     for (int j=0;j<=m;++j) g[0][j]=g[1][j],g[1][j]=0,f[0][j]=f[1][j],f[1][j]=0;
    }
    ans=max(ans,g[0][m]);
    printf("%d",ans);
    return 0;
}