【NOIP2011模拟11.1】钓鱼
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表示鱼出现的时刻(所有的数都为整数)
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
Hint
30%的数据满足 1<=N<=5 100%的数据满足 1<=T,time<=10 1<=Ax,Ay,Q,x,y,D,L<=10 1<=N<=14
题解
容易想到DP 发现数据很小，可以用状压DP 设f[i][j][k]为时间i,x坐标j,钓鱼的状态为k的最大钓鱼数
转移
1、移动：f[i+1][j-q ~ j+q][k]=f[i][j][k] 2、钓鱼：f[i+1][j][k]=f[i][j][k]+fish(i,j,k） 3、不作操作：f[i+1][j][k]=f[i][j][k]
code
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 15
using namespace std
;
int ans
,T
,mx
,my
,ax
,Q
,n
,p
[N
],q
[N
],d
[N
],l
[N
],t
[N
],f
[N
][N
][17007];
int fish(int x
,int y
,int z
){
int nl
,nr
;
for(int i
=1;i
<=n
;i
++){
if(p
[i
]==0) nr
=(x
-t
[i
])*d
[i
],nl
=nr
-l
[i
];
else nl
=mx
-(x
-t
[i
])*d
[i
],nr
=nl
+l
[i
];
if(nl
<=y
&&nr
>=y
) z
|=1<<(i
-1);
}
return z
;
}
int main(){
scanf("%d%d%d%d%d%d",&T
,&mx
,&my
,&ax
,&Q
,&n
);
for(int i
=1;i
<=n
;i
++) scanf("%d%d%d%d%d",&p
[i
],&q
[i
],&d
[i
],&l
[i
],&t
[i
]);
f
[0][ax
][0]=1;
for(int i
=0;i
<=T
+1;i
++)
for(int j
=0;j
<=mx
;j
++)
for(int s
=0;s
<=1<<n
;s
++){
if(!f
[i
][j
][s
]) continue;
int now
=0;
for(int k
=1;k
<=n
;k
++) if(s
&(1<<(k
-1))) now
++;
ans
=max(ans
,now
);
for(int k
=max(0,j
-Q
);k
<=min(mx
,j
+Q
);k
++) f
[i
+1][k
][s
]=1;
f
[i
+1][j
][fish(i
,j
,s
)]=1;
}
printf("%d",ans
);
}
