P1514引水入城解题报告

看到这题我就想着最基础的是搜索。但是搜索了之后只知道从一个临近湖边点能够到达干旱地区的点,就算储存了以后还要一个个搜索来求出最小值，太麻烦了。因为要用到数组，自然可以加上dp。 首先这很明显是bfs，搜的对象就是从一个最高点开始（也就是只可以出去的，引水引不进的）.按照前面的思路，我需要一个v[i]表示蓄水厂可以到这个点吗（0个的话就直接++）,tu[i]存图，bfs时用上一个结构体存点，当做队列。以及一个结构体，包含一排中的左端点（能到的最左的点）以及右端点，还有值v（也是判断这个临近湖的点能否被到达，如果能自然就不用建蓄水厂了）,和判断是否经过的数组f[i]。dp时用d[i]表示1—n最多要多少蓄水厂，g[i][j]表示从i到j的需要蓄水厂数。所以dp方程就是d[i]=min(d[i],d[j]+g[j+1][i])。 那些啥的我都打到代码里了，因为我发现这样直接对每条语句解释更加简洁明了。 ```cpp #include<algorithm> #include<cstring> #include<cstdio> using namespace std; int n,m,sum,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; int tu[501][501],d[501],f[501][501],v[1000001],g[501][501]; struct nodea{ int r,l,v; }a[1000001]; struct nodeb{ int x,y; }b[1000001]; int bfs(int ax,int by) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=0; if(n==1){ v[by]=1; a[by].l=a[by].r=by; }//当它只有一行时，就可以直接赋值了 int h=1,r=2,X,Y; b[1].x=ax;b[1].y=by;f[ax][by]=1; while(h<r){ for(int i=0;i<=3;i++){ X=b[h].x+dx[i];Y=b[h].y+dy[i]; if(tu[X][Y]<tu[b[h].x][b[h].y]&&f[X][Y]==0){ if(X>=1&&X<=n&&Y>=1&&Y<=m)//判断条件就不用我说了吧 { if(X==1) a[Y].v=0; //当它可以到达新的临近湖的点，那么这个点肯定不用建厂，因为这个点可以被到达 if(X==n){ v[Y]=1; a[by].l=min(a[by].l,Y); a[by].r=max(a[by].r,Y); }//更新 b[r].x=X; b[r].y=Y; f[X][Y]=0; r++; } } } h++; } } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&tu[i][j]); for(int i=1;i<=m;i++){ a[i].l=99999999; a[i].r=0; a[i].v=1; v[i]=0; } for(int i=1;i<=m;i++) if(a[i].v==1) bfs(1,i); //对于每个可以用的点进行宽搜 for(int i=1;i<=m;i++) if(v[i]==0) sum++; if(sum!=0){ printf("0\n%d",sum); return 0; }//假如有不可以到的点就直接++输出就行 for(int i=1;i<=m;i++) { d[i]=99999999; for(int j=1;j<=m;j++) g[i][j]=99999999; } for(int t=1;t<=m;t++) if(a[t].r!=0) for(int i=a[t].l;i<=a[t].r;i++) for(int j=i;j<=a[t].r;j++) { g[i][j]=1; if(i==1) d[j]=1; }//把左端点到右端点赋值为0 for(int i=1;i<=m;i++) for(int j=1;j<=i-1;j++) d[i]=min(d[i],d[j]+g[j+1][i]);//转移方程 printf("1\n%d",d[m]); return 0; } ``` PS：这题贼坑的就是4,5的点，感觉莫名其妙，数据是一堆递减数字再加上一堆1……（大佬可以帮我看一下……）