题面

分析

状压 \(dp\) 直接上啊！

设 \(f_{t,S,pos}\) 表示 \(t\) 这个时刻之前能钓到的最多的鱼的数量

那么当前为可以钓鱼也可以移动

于是一切都明朗了

\(Code\)

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

int T , Mx , My , A , Q , n , g[15][20000][15];

struct node{

	int x , y , d , l , t , f , bz;

}f[20];

int main()

{

	scanf("%d%d%d%d%d%d" , &T , &Mx , &My , &A , &Q , &n);

	for(register int i = 0; i < n; i++)

		scanf("%d%d%d%d%d" , &f[i].x , &f[i].y , &f[i].d , &f[i].l , &f[i].t) ,

		f[i].f = (f[i].x == 0) ? 1 : -1;

	memset(g , 255 , sizeof g);

	g[0][(1 << n) - 1][A] = 0;

	for(register int i = 0; i <= T; i++)

		for(register int j = 0; j < (1 << n); j++)

			for(register int k = 0; k <= Mx; k++)

			{

				if (g[i][j][k] == -1) continue;

				int res = 0 , r = 0;

				for(register int l = 0; l < n; l++)

				if (f[l].t <= i && (j & (1 << l)))

				{

					int pos = f[l].x + f[l].f * f[l].d * (i - f[l].t) ,

						tl = pos , tr = pos - f[l].f * f[l].l;

					if (tl > tr) swap(tl , tr);

					if (tl <= k && k <= tr) ++res , r += (1 << l);

				}

				g[i + 1][j - r][k] = max(g[i + 1][j - r][k] , g[i][j][k] + res);

				for(register int l = max(0 , k - Q); l <= min(Mx , k + Q); l++)

					g[i + 1][j][l] = max(g[i + 1][j][l] , g[i][j][k]);

			}

	int ans = 0;

	for(register int j = 0; j < (1 << n); j++)

		for(register int k = 0; k <= Mx; k++) ans = max(ans , g[T + 1][j][k]);

	printf("%d" , ans);

}

巴特西

JZOJ 2645. 【NOIP2011模拟11.1】钓鱼

题面

分析

\(Code\)

最新文章

热门文章