欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[NOIP模拟题]钓鱼

程序员文章站 2023-12-26 10:34:09
...

Description
我们把钓鱼的过程放在坐标系里来考虑。图中蓝色的点为船,初始时它的坐标记为(Ax,y)。河深为y,河宽为x。某个时刻会从左边界或右边界游出来一条鱼(左边的往右边游,右边的往左边游),即鱼游出来时的横坐标为0或x,这条鱼每秒会游D个单位长度,鱼的长度为L。初始时刻为0,对于每个时刻x,船可以选择花费1s向左或向右移动最多Q个单位长度,或者选择在当前位置进行钓鱼,钓鱼的动作是瞬间的,且发生在时刻x,鱼还来不及移动就被钓上了。如果选择钓鱼,那么在时刻x就不能动。{x+1时刻可以选择移动}设当前位置为z,将鱼看成一条线段,当线段与直线x=z相交时就认为鱼上钩了,所以一次钓鱼动作可能会钓多条鱼。聪明的你告诉钓鱼者,在T时刻前最多能钓多少鱼?
[NOIP模拟题]钓鱼

Input
第一行:T
第二行:MaxxMaxy,表示河宽和河深。
第三行:两个数AxQ
第四行:N,表示有N条鱼,
接下来N行描述每条鱼:每行共五个数,xyDLtime
x表示鱼头的初始位置,保证为0或maxxy表示鱼头的初始深度,time表示鱼出现的时刻(所有的数都为整数)
1<=T,time<=10
1<=Ax,Ay,Q,x,y,D,L<=10
1<=N<=14

Output
只有一行:ans,表示最多的钓鱼数。

Sample Input
3
4 5
4 1
3
0 1 3 1 0
4 2 2 1 0
0 3 3 1 2

Sample Output
3

样例解释
在第0时刻,船移动到3号位置。第1时刻在当前位置钓鱼,钓上1号和2号鱼。第2时刻在当前位置静止不动。第3时刻,在当前位置钓鱼,钓上3号鱼,共钓上3条鱼。

思路
河的深度和鱼的深度根本没有什么用。首先求出每个时间点,每个位置能钓到哪些鱼,压到一个数中。令fi,j,S表示第i个时间点,第j个位置,能否钓到S的二进制状态表示的鱼。显然,每个状态要么钓一次鱼,要么移动一段距离。那么状态转移方程。。。看代码吧。

代码

#include <cstdio>
#include <algorithm>

const int maxn=14;
const int maxt=10;

int t,x,y,n,sx,q,ans;
int fish[maxt+1][maxt+1],f[maxt+1][maxt+1][1<<maxn];

int calc(int x)
{
    int res=0;
    while(x)
    {
        res+=x&1;
        x>>=1;
    }
    return res;
}

int main()
{
    scanf("%d%d%d%d%d%d",&t,&x,&y,&sx,&q,&n);
    for(int i=1; i<=n; i++)
    {
        int a,b,d,l,time;
        scanf("%d%d%d%d%d",&a,&b,&d,&l,&time);
        for(int j=time; j<=t; j++)
        {
            int left,right;
            if(a==0)
            {
                left=std::max(0,(j-time)*d-l);
                right=std::min(x,(j-time)*d);
            }
            if(a==x)
            {
                left=std::max(0,x-(j-time)*d);
                right=std::min(x,x-(j-time)*d+l);
            }
            for(int k=left; k<=right; k++)
            {
                fish[j][k]|=1<<(i-1);
            }
        }
    }
    f[0][sx][fish[0][sx]]=1;
    for(int i=-q; i<=q; i++)
    {
        if((sx+i>=0)&&(sx+i<=x))
        {
            f[0][sx+i][0]=1;
        }
    }
    for(int i=0; i<t; i++)
    {
        for(int j=0; j<=x; j++)
        {
            for(int k=0; k<1<<n; k++)
            {
                if(f[i][j][k])
                {
                    f[i+1][j][k|fish[i+1][j]]=1;//钓鱼
                    for(int h=-q; h<=q; h++)
                    {
                        if((j+h>=0)&&(j+h<=x))
                        {
                            f[i+1][j+h][k]=1;//移动
                        }
                    }
                    ans=std::max(ans,calc(k));
                }
            }
        }
    }
    for(int i=0; i<=x; i++)
    {
        for(int j=1; j<1<<n; j++)
        {
            if(f[t][i][j])
            {
                ans=std::max(ans,calc(j));
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

上一篇:

下一篇: