NOIP2014 飞扬的小鸟

Description：

挺有意思的一道题，就是细节挺多的qwq

Solution：

初步的想法是设 \(f_{i,j}\) 表示坐标在 \((i,j)\) 时的最少点击次数。

\[f_{i,j}=min(f_{i-1,j+y_i},f_{i-1,j-x_i},f_{i,j-x_i})\]

但是写完了之后我发现有一个问题就是不能同时转移第一项和最后一项。

可以先转移完上升的情况在转移下降的情况。但还有一种好像好写的做法就是设 \(f_{i,j,1/0}\) 表示坐标为 \((i,j)\) 且当前状态是从上升/下降转移过来的最少点击次数。

就好了

Code:

#include<bits/stdc++.h>
using namespace std;

const int inf = 1e9;
const int N = 10010;
const int M = 1010;
int n,m,k,ans=inf;
int f[N][M][2],vis[N][M];
int x[N],y[N];
int p[N],l[N],h[N];

void Debug()
{
    for(int i=m;i>=1;--i,putchar('\n'))
    {
        for(int j=0;j<=n;++j)
        {
            if(vis[j][i]) putchar('|');
            else if(f[j][i][0]>=inf) printf("*");
            else printf("%d",f[j][i][0]);
            printf("   ");
        }
    }
    printf("\n");
    for(int i=m;i>=1;--i,putchar('\n'))
    {
        for(int j=0;j<=n;++j)
        {
            if(vis[j][i]) putchar('|');
            else if(f[j][i][1]>=inf) printf("*");
            else printf("%d",f[j][i][1]);
            printf("   ");
        }
    }
    printf("\n---------------------------------------------------------\n\n");
}

void qsort(int l1,int r)
{
    int i=l1,j=r,mid=p[(l1+r)/2];
    while(i<=j)
    {
        while(p[i]<mid) ++i;
        while(p[j]>mid) --j;
        if(i<=j)
        {
            swap(p[i],p[j]);swap(l[i],l[j]);swap(h[i],h[j]);
            ++i;--j;
        }
    }
    if(l1<j) qsort(l1,j);
    if(i<r) qsort(i,r);
}

void init()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=k;++i) scanf("%d%d%d",&p[i],&l[i],&h[i]);
    qsort(1,k);
//  for(int i=1;i<=k;++i) printf("%d %d %d\n",p[i],l[i],h[i]);
    for(int i=1;i<=k;++i)
    {
        for(int j=1;j<=l[i];++j) vis[p[i]][j]=1;
        for(int j=h[i];j<=m;++j) vis[p[i]][j]=1;
        vis[p[i]][0]=i;
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            f[i][j][0]=f[i][j][1]=inf;
}

int check()
{
    int ret=n;
    for(int i=n;i>=1;--i)
    {
        int flag=0;
        for(int j=1;j<=m;++j)
            if(f[i][j][0]<inf||f[i][j][1]<inf)
                {flag=1;break;}
        if(flag) {ret=i;break;}
    }
    while(!vis[ret][0]) --ret;
    return vis[ret][0];
} 

int main()
{
    init();
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<m;++j)
        {
            if(vis[i][j]) continue;
            if(j+y[i]<=m) f[i][j][0]=min(f[i-1][j+y[i]][0],f[i-1][j+y[i]][1]);
            if(j-x[i]>0) f[i][j][1]=min(min(f[i-1][j-x[i]][0],f[i-1][j-x[i]][1]),f[i][j-x[i]][1])+1;
        }
        if(!vis[i][m]) for(int j=m;j>=m-x[i];--j)
        {
            f[i][m][1]=min(min(f[i][m][1],f[i][j][1]+1),min(f[i-1][j][0],f[i-1][j][1])+1);
        }
        ans=inf;
        for(int j=1;j<=m;++j) ans=min(ans,min(f[i][j][0],f[i][j][1]));
        if(ans>=inf) {printf("0\n%d\n",vis[i][0]-1);return 0;}
    }

//  Debug();

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

NOIP2014 飞扬的小鸟

原文：https://www.cnblogs.com/oierwyh/p/12284090.html