记录编号	457165	评测结果	AAAAAAAAAA
题目名称	[FZYZOJ 1273] 坦克游戏	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.220 s
提交时间	2017-10-06 21:08:03	内存使用	40.40 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=60;
int n,m,r,t,a[1010][1010],q[100010],size;
int dp[N][N][2610];
//规定，攻击目标只在目标第一次进入视野时
//dp[i][j][t]表示，坦克在(i,j)，用了t秒的最大得分
//一次移动，新扩大的视野只有1*(2*r+1)大小
bool cmp(int x,int y){return x>y;}
int main()
{
	freopen("gametk.in","r",stdin);
	freopen("gametk.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&r,&t);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
		scanf("%d",&a[i][j]);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	for (int k=0;k<=t;k++)
		dp[i][j][k]=-1e9;
	size=0;
	for (int i=1;i<=r+1&&i<=n;i++)
	for (int j=1;j<=r+1&&j<=m;j++)
		q[++size]=a[i][j];
	sort(q+1,q+size+1,cmp);
	dp[1][1][0]=0;
	for (int i=1;i<=size&&i<=t;i++) dp[1][1][i]=dp[1][1][i-1]+q[i];
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++){
		if (i<n){//向下移动
			size=0;
			for (int p=max(j-r,1);p<=j+r;p++) q[++size]=a[i+r+1][p];
			sort(q+1,q+size+1,cmp);
			for (int p=1;p<=size;p++) q[p]+=q[p-1];
			for (int k=0;k<t;k++)
			for (int l=0;l<=size&&l+k<t;l++)
				dp[i+1][j][k+l+1]=max(dp[i+1][j][k+l+1],dp[i][j][k]+q[l]);
		}
		if (j<m){//向右移动
			size=0;
			for (int p=max(i-r,1);p<=i+r;p++) q[++size]=a[p][j+r+1];
			sort(q+1,q+size+1,cmp);
			for (int p=1;p<=size;p++) q[p]+=q[p-1];
			for (int k=0;k<t;k++)
			for (int l=0;l<=size&&l+k<t;l++)
				dp[i][j+1][k+l+1]=max(dp[i][j+1][k+l+1],dp[i][j][k]+q[l]);
		}
	}
	int ans=0;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	for (int k=0;k<=t;k++)
		ans=max(ans,dp[i][j][k]);
	printf("%d\n",ans);
	return 0;
}