C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2023-01-27 20:10:50

#include <iostream>
using namespace std;

typedef long long ll;
int n, m, x, y;
int w[9][9];
ll k, res, sum;

void dfs(int x, int y, int pos, ll q)
{
    if (x < 1 || x > n || y < 1 || y > m) return ;
//     cout << x << ' ' << y << ' ' << q << endl;
    res = max(res, q + w[x][y]);
    if (pos == 1) return ;
    int temp = w[x][y];
    w[x][y] = 0;
    dfs(x - 1, y, pos - 1, q + temp);
    dfs(x + 1, y, pos - 1, q + temp);
    dfs(x, y - 1, pos - 1, q + temp);
    dfs(x, y + 1, pos - 1, q + temp);
    w[x][y] = temp;
}

int main()
{
    cin >> n >> m >> x >> y >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &w[i][j]), sum += w[i][j];
    
    if (k >= n * m) printf("%lld", sum + n * m * (n * m - 1) / 2 + (k - n * m) * n * m);
    else {
        dfs(x, y, k, 0);
        cout << res + k * (k - 1) / 2;
    }
}

C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 488K, 提交时间: 2020-02-02 13:45:49

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,T,S,i,j,a[15][15],d[5][2]={{-1,0},{1,0},{0,-1},{0,1},{0,0}};
long long k,Ans;
void sk(int u,int v,int step,long long eng){
    long long _eng=eng+a[u][v]+step-1;
    int tmp=a[u][v];
    if(step>=k){Ans=max(Ans,_eng);return;}
    a[u][v]=1-step;
    for(int i=0;i<5;++i){
        int _u=u+d[i][0],_v=v+d[i][1];
        if(!(1<=_u&&_u<=n&&1<=_v&&_v<=m))continue;
        sk(_u,_v,step+1,_eng);
    }
    a[u][v]=tmp;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>x>>y>>k;
    for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)cin>>a[i][j];
    if(k<n*m){
        sk(x,y,1,0);
    }else{
        for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)S+=a[i][j];
        T=n*m;
        Ans=S+T*(T-1)/2+(k-T)*T;
    }
    cout<<Ans;
}

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 472K, 提交时间: 2020-02-02 19:03:52

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int n,m,x,y;ll k;
ll a[15][15],vis[15][15];ll ans;
void dfs(int xx,int yy,ll pos,ll now){
	if(pos==k){
		ans=max(ans,now);return;
	}
	if(xx<=0||xx>n||yy<=0||yy>m) return;
	ll rem=a[xx][yy]+pos-vis[xx][yy];
	vis[xx][yy]+=rem;
	for(int i=0;i<4;i++){
		dfs(xx+dir[i][0],yy+dir[i][1],pos+1,now+rem);
	}vis[xx][yy]-=rem;
}
int main(){
	scanf("%d%d%d%d%lld",&n,&m,&x,&y,&k);ans=0;ll sum=0;memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&a[i][j]);sum+=a[i][j];
		}
	}if(k<n*m){
		dfs(x,y,0,0);
		printf("%lld\n",ans);
	}else{
		ll st=k-n*m;
		printf("%lld\n",(st+st+n*m-1)*(ll)n*(ll)m/2+sum);
	}
}