[NOIP模拟题]钓鱼

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

Input
第一行：T。
第二行：Maxx，Maxy，表示河宽和河深。
第三行：两个数Ax和Q。
第四行：N，表示有N条鱼，
接下来N行描述每条鱼：每行共五个数，x，y，D，L，time。
x表示鱼头的初始位置，保证为0或maxx，y表示鱼头的初始深度，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;
}