题面

题目描述

我们把钓鱼的过程放在坐标系里来考虑。图中蓝色的点为船，初始时它的坐标记为

(Ax,y)。河深为y，河宽为x。某个时刻会从左边界或右边界游出来一条鱼(左边的往右边游，

右边的往左边游)，即鱼游出来时的横坐标为0或x，这条鱼每秒会游D个单位长度，鱼的长

度为L。初始时刻为0，对于每个时刻x，船可以选择花费1s向左或向右移动最多Q个单位

长度，或者选择在当前位置进行钓鱼，钓鱼的动作是瞬间的，且发生在时刻x，鱼还来不及

移动就被钓上了。如果选择钓鱼，那么在时刻x就不能动。{x+1时刻可以选择移动}设当前

位置为z，将鱼看成一条线段，当线段与直线x=z相交时就认为鱼上钩了，所以一次钓鱼动

作可能会钓多条鱼。

聪明的你告诉钓鱼者，在T时刻前最多能钓多少鱼?

输入

第一行：T

第二行：Maxx,Maxy,表示河宽和河深

第三行：两个数Ax,Q

第四行：N，表示有N条鱼

接下来N行描述每条鱼：每行共五个数，x,y,D,L,time

x表示鱼头的初始位置，保证为0或maxx，y表示鱼头的初始深度，time表示鱼出现的时

刻(所有的数都为整数)

输出

只有一行：ans，表示最多的钓鱼数

样例输入

3 4 5 4 1 3 0 1 3 1 0 4 2 2 1 0 0 3 3 1 2

样例输出

3

数据范围

100%的数据满足

1<=T,time<=10

1<=Ax,Ay,Q,x,y,D,L<=10

1<=N<=14

30%的数据满足

1<=N<=5

题解

这题一看N和T的数据范围，只有14，可直接状压，不想打DP就和我一样记忆化搜索。搜索时传三个参数（DP同理）为x,y,z，其中x表示当前的位置（范围为1-maxn），y表示当前的时间（范围为0-t），z为n条鱼是否已被钓走，初值为（1<<n)-1。

然后每到一个地方有两种选择：

1、在原地不动，并钓鱼，即memory[x][y][z]（但前状态记忆化）=search(x,y+1,z)+能钓到的鱼的条数。

2、向左或向右走（q以内）的最大值：memory[x][y][z]=max(memory[x][y][z],max(search(x-i,y+1,z),search(x+i,y+1,z)))（显然，鱼的状态因为你没有钓它，所以不会变。

注意0时刻也可以选择

代码

代码如下

#include<bits/stdc++.h> using namespace std; int i,j,n,m,xz,q,k,l,o,p,fish[15][15][2],memory[15][15][16390],t; int pd(int xx,int yy,int zz) { int cnt=0; for (int y=k;y>=1;y--) { if ((zz>>y-1)%2==1&&fish[y][yy][0]<=xx&&xx<=fish[y][yy][1]) { cnt++; } } return cnt; } int cl(int xx,int yy,int zz) { for (int y=k;y>=1;y--) { if ((zz>>y-1)%2==1&&fish[y][yy][0]<=xx&&xx<=fish[y][yy][1]) { zz-=(1<<y-1); } } return zz; } int ss(int wz,int st,int zt) { if (st>t||wz<0||wz>n) return 0; if (memory[wz][st][zt]!=0) { return memory[wz][st][zt]; } else { memory[wz][st][zt]=pd(wz,st,zt)+ss(wz,st+1,cl(wz,st,zt)); for (int x=1;x<=q;x++) { memory[wz][st][zt]=max(ss(wz-x,st+1,zt),max(ss(wz+x,st+1,zt),memory[wz][st][zt])); } return memory[wz][st][zt]; } } int main() { scanf("%d",&t); scanf("%d %d",&n,&m); scanf("%d %d",&xz,&q); scanf("%d",&k); for (i=1;i<=k;i++) { int a,a2,a3,a4,a5; scanf("%d %d %d %d %d",&a,&a2,&a3,&a4,&a5); for (j=0;j<a5;j++) { fish[i][j][1]=-1; } if (a==n) { for (o=j;o<=t;o++) { fish[i][o][0]=a-(o-j)*a3; fish[i][o][1]=fish[i][o][0]+a4; } } else { for (o=j;o<=t;o++) { fish[i][o][1]=(o-j)*a3; fish[i][o][0]=fish[i][o][1]-a4; } } } memory[xz][0][(1<<k)-1]=ss(xz,0,(1<<k)-1); printf("%d",memory[xz][0][(1<<k)-1]); }

码风有点丑，请见谅。