首页 > 代码库 > bzoj3087: Coci2009 misolovke
bzoj3087: Coci2009 misolovke
Description
[misolovke]
给定一个 N*N 的网格.
每个格子里至少会有一个捕鼠器, 并且已知每个格子里的捕鼠器个数.现在需要在 每一行 中选取恰好 K 个连续的格子, 把里面的捕鼠器全部拿走, 并且需要满足
老鼠不能 从网格最左边到网格最右边
也不能 从网格最上面到网格最下面
老鼠行走的方向是 上下左右 4个方向
老鼠只能经过没有捕鼠器的格子
求拿走捕鼠器个数的最大值
Input
第1行: 2 个整数 N, K (2 <= N <= 250, 1 <= K <= N/2)
第2..N+1行: 每行 N 个整数. 表示网格中每个格子里的捕鼠器个数.
Output
第1行: 仅一个整数, 表示拿走捕鼠器个数的最大值
dp，f[i][j][S]表示考虑了前i行，第i行决策为[j-k+1,j]，当前决策和左，右，上边界是否联通，捕鼠器的最大个数，转移的时候去掉不合法状态（同时与左右联通或最后一行与上边界联通）
#include<cstdio>int n,k,v[253];int f[253][253][8];int _(){ int x=0,c=getchar(); while(c<48)c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x;}void maxs(int&a,int b){if(a<b)a=b;}bool chk(int x){return (x&3)!=3;}int main(){ n=_();k=_(); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j)v[j]=_()+v[j-1]; for(int j=k;j<=n;++j){ int s=v[j]-v[j-k]; for(int d=0;d<8;++d)f[i][j][d]=-0x7fffffff; int w=0; if(j==k)w|=1; if(j==n)w|=2; if(i==1)w|=4; for(int a=k;a<=n;++a){ if(j>a-k&&j<a+k){ for(int d=0;d<8;++d)if(chk(d|w))maxs(f[i][j][d|w],f[i-1][a][d]+s); }else{ if(chk(w))for(int d=0;d<8;++d)maxs(f[i][j][w],f[i-1][a][d]+s); } } } } int ans=-0x7fffffff; for(int i=k;i<=n;++i)for(int d=0;d<4;++d)maxs(ans,f[n][i][d]); printf("%d",ans); return 0;}
bzoj3087: Coci2009 misolovke
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。