首页 > 代码库 > BZOJ1897 : tank 坦克游戏
BZOJ1897 : tank 坦克游戏
设$f[i][j][k]$表示坦克位于$(i,j)$，目前打了不超过$k$个位置的最大得分。
初始值$f[1][1][k]$为在$(1,1)$射程内最大$k$个位置的分数总和。
对于每次移动，会新增一行或者一列$O(R)$个位置，那么显然也是从大到小取。
暴力转移是$O(R)$的，不能接受，但是注意到这是个凸函数，故存在决策单调性，分治求解即可。
$ans=\max(f[i][j][T-i-j+2])$
时间复杂度$O(nm(T+R\log R))$。
#include<cstdio>#include<algorithm>using namespace std;const int N=505,M=255;int T,n,m,R,_n,_m,lim,o,i,j,k,a[N][N],f[2][N][M],g[M],v[M],q[N*N],cnt,ans;inline bool cmp(int x,int y){return x>y;}inline void up(int&x,int y){if(x<y)x=y;}void solve(int l,int r,int dl,int dr){ int m=(l+r)>>1,dm=dl,&f=v[m]; for(int i=dl;i<=dr&&i<=m;i++){ int t=g[m-i]+q[i]; if(t>f)f=t,dm=i; } if(l<m)solve(l,m-1,dl,dm); if(r>m)solve(m+1,r,dm,dr);}int main(){ scanf("%d%d%d%d",&n,&m,&R,&T); for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]); _n=max(1,n-R),_m=max(1,m-R); for(i=1;i<=n&&i<=R+1;i++)for(j=1;j<=m&&j<=R+1;j++)if(a[i][j]>0)q[++cnt]=a[i][j]; if(cnt){ sort(q+1,q+cnt+1,cmp); for(i=1;i<=cnt&&i<=T;i++)f[1][1][i]=f[1][1][i-1]+q[i]; for(;i<=T;i++)f[1][1][i]=f[1][1][i-1]; } for(i=o=1;i<=_n;i++,o^=1)for(j=1;j<=_m;j++){ lim=T-i-j+2; if(lim<=0)continue; if(i>1){ for(k=0;k<=lim;k++)g[k]=v[k]=f[o^1][j][k]; cnt=0; if(i+R<=n)for(k=max(1,j-R);k<=m&&k<=j+R;k++)if(a[i+R][k]>0)q[++cnt]=a[i+R][k]; if(cnt){ sort(q+1,q+cnt+1,cmp); for(k=1;k<=cnt;k++)q[k]+=q[k-1]; solve(1,lim,0,cnt); } for(k=0;k<=lim;k++)f[o][j][k]=v[k]; } if(j>1){ for(k=0;k<=lim;k++)g[k]=v[k]=f[o][j-1][k]; cnt=0; if(j+R<=m)for(k=max(1,i-R);k<=n&&k<=i+R;k++)if(a[k][j+R]>0)q[++cnt]=a[k][j+R]; if(cnt){ sort(q+1,q+cnt+1,cmp); for(k=1;k<=cnt;k++)q[k]+=q[k-1]; solve(1,lim,0,cnt); } for(k=0;k<=lim;k++)up(f[o][j][k],v[k]); } up(ans,f[o][j][lim]); } return printf("%d",ans),0;}
BZOJ1897 : tank 坦克游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。