[Luogu] 飞扬的小鸟

https://www.luogu.org/problemnew/show/P1941

Bfs or Dp

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + ;

#define gc getchar()

#define oo 99999999

struct Node_1 {

    int X, D, U;

} P[N];

struct Node_2 {

    int U, D;

} M[N];

struct node {

    int x, y, step;

};

int n, m, k;

int Answer = oo, Maxx;

queue <node> Q;

inline int read() {

    int x = ;

    char c = gc;

    while(c < '' || c > '') c = gc;

    while(c >= '' && c <= '') x = x *  + c - '', c = gc;

    return x;

}

int up, down;

int vis[N][];

inline void Bfs() {

    for(int i = m; i >= ; i --) {

        node now;

        now.x = ;

        down = i - M[].D, up = i + M[].U;

        if(down > P[].D && down < P[].U && vis[][down] == ) {

            now.y = down;

            now.step = ;

            vis[now.x][now.y] = ;

            Q.push(now);

        }

        if(up > P[].D && up < P[].U && vis[][up] == ) {

            now.y = min(up, m);

            vis[now.x][now.y] = ;

            now.step = ;

            Q.push(now);

        }

    }

    while(!Q.empty()) {

        node topp = Q.front();

        Q.pop();

        Maxx = max(Maxx, topp.x);

        if(topp.x == n + ) {

            Answer = min(Answer, topp.step);

            continue ;

        }

        int y = topp.y, x = topp.x;

        node nxt;

        nxt.x = x + ;

        down = y - M[x].D, up = y + M[x].U;

        if(down > P[x + ].D && down < P[x + ].U) {

            nxt.y = down;

            nxt.step = topp.step;

            if(vis[nxt.x][nxt.y] == ) {

                vis[nxt.x][nxt.y] = nxt.step;

                Q.push(nxt);

            } else {

                if(vis[nxt.x][nxt.y] > nxt.step) {

                    Q.push(nxt);

                    vis[nxt.x][nxt.y] = nxt.step;

                }

            }

        }

        nxt.y = up;

        nxt.step = topp.step;

        up = min(up, m);

        while(up > P[x + ].D && up < P[x + ].U) {

            nxt.y = min(nxt.y, m);

            if(vis[nxt.x][nxt.y] == ) {

                nxt.step ++;

                vis[nxt.x][nxt.y] = nxt.step;

                Q.push(nxt);

            } else {

                if(vis[nxt.x][nxt.y] > nxt.step + ) {

                    nxt.step ++;

                    Q.push(nxt);

                    vis[nxt.x][nxt.y] = nxt.step;

                }

            }

            if(nxt.y == m) break;

            nxt.y += M[x].U;

            up = min(nxt.y, m);

        }

    }

}

int main() {

    n = read();

    m = read();

    k = read();

    for(int i = ; i <= n; i ++)

        M[i].U = read(), M[i].D = read(), P[i].U = m + ;

    P[n + ].U = m + ;

    for(int i = ; i <= k; i ++) {

        int X = read() + ;

        P[i].X = X;

        P[X].D = read();

        P[X].U = read();

    }

    Bfs();

    if(Answer != oo) cout <<  << "\n" << Answer;

    else {

        cout <<  << "\n";

        int js();

        for(int i = ; i <= k; i ++) if(P[i].X <= Maxx) js ++;

        cout << js;

    }

    return ;

}

/*

5 5 0

3 3

2 1

2 3

2 1

3 2

*/

#include<cstdio>

#include<cctype>

#include<algorithm>

#define N 10003

#define M 1003

#define For(i,j,k) for(int i=j;i<=k;++i)

int read() {

    int x=,l=;

    char ch=getchar();

    while(!isdigit(ch)) {

        if (ch=='-') l=-;

        ch=getchar();

    }

    while(isdigit(ch)) x=x*+(ch^),ch=getchar();

    return x*l;

}

using namespace std;

int a[N][M],x[N],y[N],hi[N]; //a存到当前点的最优步数

short hk[M<<],wal[M<<]; //hk记列,wal记行,这只是循环队列,不要在意变量名

bool fl[N][M],mp[N][M],li[N]; //fl--某个点有没有被走过,mp--某个点有没有管子,li--记录某一列能不能到

int main() {

    int an,n=read(),m=read(),k=read(),mo,ha,jzm,l=,r,ac,p=,kk,ff;

    ac=m<<;

    For(i,,n-) x[i]=read(),y[i]=read(),hi[i]=; //hi记录某一列上限,如果是最大值表示无上限

    For(i,,k) {

        jzm=read(),mo=read(),ha=read(); //不要在意变量名x2

        For(j,,mo) mp[jzm][j]=;

        For(j,ha,m) mp[jzm][j]=;

        hi[jzm]=ha-; //mp,hi标记

    }

    r=m;

    For(i,,m) wal[i]=i; //第0列入队

    while(l<r) {

        l++;

        mo=hk[l%ac];

        ha=wal[l%ac];

        ff=an=;

        li[mo]=;

        if (mo==n) continue;

        kk=min(m,hi[mo+]);

        for(int i=ha+x[mo]; i<=kk; i+=x[mo]) { //枚举当前点可以到的点

            an++;

            if (mp[mo+][i]) continue; //判断当前有没有管道(下面的,碰上面管道就退循环了)

            if (!fl[mo+][i]) { //没走过就入队

                fl[mo+][i]=;

                r++;

                hk[r%ac]=mo+;

                wal[r%ac]=i;

                a[mo+][i]=a[mo][ha]+an;

            } else if (a[mo+][i]>a[mo][ha]+an) a[mo+][i]=a[mo][ha]+an; //更新值

            if (fl[mo][i]&&a[mo][i]<=a[mo][ha]+an) {

                ff=;

                break;

            }

            //重要剪枝!如果当前点顶上有点比他更优那就可以退了

            //但是在这之前的循环是必要的,因为这时走的点是他顶上那个点走不到的

        }

        if (!mp[mo+][m]&&!ff) { //特判到顶的情况

            if (!fl[mo+][m]) {

                fl[mo+][m]=;

                r++;

                hk[r%ac]=mo+;

                wal[r%ac]=m;

                a[mo+][m]=a[mo][ha]+an+;

            } else if (a[mo+][m]>a[mo][ha]+an+) a[mo+][m]=a[mo][ha]+an+;

        }

        if (ha-y[mo]>) { //特判下降情况

            jzm=ha-y[mo];

            if (!mp[mo+][jzm]) {

                if (!fl[mo+][jzm]) {

                    fl[mo+][jzm]=;

                    r++;

                    hk[r%ac]=mo+;

                    wal[r%ac]=jzm;

                    a[mo+][jzm]=a[mo][ha];

                } else if (a[mo+][jzm]>a[mo][ha]) a[mo+][jzm]=a[mo][ha];

            }

        }

    }

    for(int i=n; i>=; i--) //输出

        if (li[i]) {

            if (i==n) {

                printf("1\n");

                an=;

                For(j,,m) if (an>a[n][j]&&fl[n][j]) an=a[n][j];

                printf("%d\n",an);

                return ;

            }

            printf("0\n");

            an=;

            for(int j=i; j>=; j--) if (hi[j]!=) an++;

            printf("%d\n",an);

            return ;

        }

}

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int MAXDP=;

int l[],h[];

int dp[][];

int x[],y[];

bool p[];

int main() {

    int n,i,j,k,m,w;

    scanf("%d%d%d",&n,&m,&k);

    for(i=; i<n; i++) {

        scanf("%d%d",&x[i],&y[i]);

        l[i]=;

        h[i]=m+;

    }

    l[n]=;

    h[n]=m+;

    for(i=; i<k; i++) {

        scanf("%d",&w);

        scanf("%d%d",&l[w],&h[w]);

        p[w]=true;

    }

    for(i=; i<=n; i++) {

        for(j=; j<=m; j++) {

            dp[i][j]=MAXDP;

        }

    }

    dp[][]=MAXDP;

    for(i=; i<=m; i++) {

        dp[][i]=;

    }

    for(i=; i<=n; i++) {

        for(j=x[i-]; j<=m; j++) {

            if(j==m) {

                for(w=m-x[i-]; w<=m; w++) {

                    dp[i][j]=min(dp[i][j],dp[i-][w]+);

                    dp[i][j]=min(dp[i][j],dp[i][w]+);

                }

            }

            dp[i][j]=min(dp[i][j],dp[i-][j-x[i-]]+);

            dp[i][j]=min(dp[i][j],dp[i][j-x[i-]]+);

        }

        for(j=max(,l[i]+); j<=min(m-y[i-],h[i]-); j++) {

            dp[i][j]=min(dp[i][j],dp[i-][j+y[i-]]);

        }

        for(j=l[i]; j>=; j--) {

            dp[i][j]=MAXDP;

        }

        for(j=h[i]; j<=m; j++) {

            dp[i][j]=MAXDP;

        }

    }

    int ans=MAXDP;

    int cnt=k;

    for(i=n; i>=; i--) {

        for(j=l[i]+; j<=h[i]-; j++) {

            ans=min(ans,dp[i][j]);

        }

        if(ans<MAXDP) {

            break;

        }

        if(p[i]==true) {

            k--;

        }

    }

    if(cnt==k) {

        printf("1\n%d",ans);

    } else {

        printf("0\n%d",k);

    }

    return ;

}

巴特西

[Luogu] 飞扬的小鸟

最新文章

热门文章