求剪枝优化

回复帖子

@wmq2006 2020-03-26 19:26 回复

P1514引水入城

代码T了大数据只有90分。。。

求剪枝优化

代码:

#include<bits/stdc++.h>
using namespace std;
int m,n,a[1001][1001],f[1001][1001]={0},t,is[501][501]={0},cnt=0,dp[1001],ans=1e9,ti=0;
int x[5]={0,0,-1,0,1},y[5]={0,-1,0,1,0};
inline int read()
{
    int x=0,ff=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') ff=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*ff;
}
struct shui{
    int l,r;
}sh[1001];
void bfs(int t){
    queue<int> qx,qy;
    qx.push(n),qy.push(t);
    while(qx.empty()==0){
        //ti+=1;
        int fx=qx.front(),fy=qy.front();
        is[fx][fy]=1;
        if(fx==1)f[t][fy]=1;
        for(int i=1;i<=4;i++){
            if(fx+x[i]>0&&fy+y[i]>0&&fy+y[i]<=m&&fx+x[i]<=n&&a[fx+x[i]][fy+y[i]]>a[fx][fy]&&is[fx+x[i]][fy+y[i]]==0){
                qx.push(fx+x[i]);
                qy.push(fy+y[i]);
            }
        }
        qx.pop(),qy.pop();
    }
}
bool cmp(shui a,shui b){
    return a.l<b.l;
}
int main(){
    cin.sync_with_stdio(false);
    for(int i=1;i<=1000;i++)dp[i]=1e9;
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
        }
    }
    for(int i=1;i<=m;i++){
        memset(is,0,sizeof(is));
        t=i;
        bfs(t);
    }
    //cout<<ti<<endl;
    for(int i=1;i<=m;i++){
    int flag=0;
        for(int j=1;j<=m;j++){
            if(f[i][j]==1)flag=1;
        }
        if(flag==1)cnt+=1;
    }
    if(cnt!=m){cout<<0<<endl<<m-cnt<<endl;return 0;}
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            if(f[j][i]==1){sh[i].l=j;break;}
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=m;j>=1;j--){
            if(f[j][i]==1){sh[i].r=j;break;}
        }
    }
    sort(sh+1,sh+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(sh[i].l==1)dp[i]=1;
        else{
            for(int j=1;j<i;j++){
                if(sh[i].l<=sh[j].r||sh[i].l-sh[j].r==1)dp[i]=min(dp[i],dp[j]+1);
            }
        }
        if(sh[i].r==m)ans=min(ans,dp[i]);
    }
    cout<<1<<endl<<ans<<endl;
    return 0;
}
@Alpha  2020-03-26 19:30 回复 举报

@wmq2006 并看不懂你在写什么,我的代码

#include <bits/stdc++.h>
using namespace std;
const int MAX_N=505;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
int H[MAX_N][MAX_N];
int n,m;
bool vis[MAX_N][MAX_N];
int L[MAX_N],R[MAX_N];
bool ok[MAX_N];
int to[MAX_N];
void DFS(int x,int y)
{
    if(x<0 || x>=n || y<0 || y>=m)return;
    if(vis[x][y])return;
    vis[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i],ty=y+dy[i];
        if(H[tx][ty]<H[x][y])DFS(tx,ty);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>H[i][j];
        }
    }
    for(int i=0;i<m;i++)
    {
        memset(vis,0,sizeof(vis));
        DFS(0,i);
        L[i]=m-1,R[i]=-1;
        for(int j=0;j<m;j++)if(vis[n-1][j])L[i]=min(L[i],j),R[i]=max(R[i],j);
        for(int j=0;j<m;j++)ok[j]|=vis[n-1][j];
    }
    if(*min_element(ok,ok+m)!=1)
    {
        cout<<0<<endl;
        int ret=0;
        for(int i=0;i<m;i++)ret+=ok[i];
        cout<<m-ret<<endl;
        return 0;
    }
    cout<<1<<endl;
    for(int i=0;i<m;i++)to[L[i]]=max(to[L[i]],R[i]);
    for(int i=1;i<m;i++)to[i]=max(to[i],to[i-1]);
    int mx=0,ans=0;
    while(mx<m)
    {
        mx=to[mx]+1;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}
@wmq2006 2020-03-26 19:56 回复 举报

@Alpha 误会误会,我的意思是说,这个题有没有什么剪枝办法。附上代码只是个人习惯,并没有要求调

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。