小Q最近迷上了一款寻宝游戏,这款游戏中每局都会生成一个n×mn×m的网格地图,从上往下依次编号为第11行到第nn行,从左往右依次编号为第11列到第mm列。每个格子上都有不同数量的金币,第ii行第jj列的格子上的金币数量为ai,jai,j。
小Q一开始位于(1,1)(1,1),每次他可以往右或者往下走,每当他经过某个格子时,他就可以拿走这个格子上的所有金币。小Q不能走出这个地图,当小Q不能再行动时,游戏结束。显然当且仅当小Q位于(n,m)(n,m)时,游戏才会结束。
一轮游戏的得分为这一轮中收集到的金币总量,而在游戏开始前,因为小Q是超级VIP用户,所以他有kk次机会交换某两个格子中的金币数。这kk次机会不一定要用完,请写一个程序帮助小Q在一轮内拿到尽可能多的金币。
Input
第一行包含一个正整数T(1≤T≤10)T(1≤T≤10),表示测试数据的组数。
每组数据第一行包含三个整数n,m,k(2≤n,m≤50,0≤k≤20)n,m,k(2≤n,m≤50,0≤k≤20),分别表示地图的长宽以及交换的次数。
接下来nn行,每行mm个整数ai,j(0≤ai,j≤106)ai,j(0≤ai,j≤106),依次表示每个格子中金币的数量。
Output
对于每组数据,输出一行一个整数,即能收集到的金币数量的最大可能值。
Sample Input
2
3 4 0
1 2 3 4
9 8 7 6
5 4 7 2
5 5 1
9 9 9 0 0
0 0 9 0 0
0 0 0 0 0
0 0 9 0 0
9 0 9 9 9
Sample Output
34
81
#include<iostream>
using namespace std;
inline bool cmp(int x,int y){
return x>y;
}
const int max1=55;
const int max2=25;
const int inf=0x3f3f3f3f;
int n,m,k;
int dp[max1][max1][max2][max2];
int a[max1][max1];
int tot;
int b[max1];
int main(){
int t;
cin>>t;
while(t--){
memset(dp,-0x3f,sizeof(dp));
cin>>n>>m>>k;
for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>a[i][j];
dp[0][0][0][0]=a[0][0];
dp[0][0][0][1]=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i==0&j==0) continue;
tot=0;
if(i) for(int y=j+1;y<m;y++) b[tot++]=a[i-1][y];
for(int x=0;x<j;x++) b[tot++]=a[i][x];
sort(b,b+tot,cmp);
for(int used=0;used<=k;used++){
for(int bal=0;bal<i+j+1&&bal<=k;bal++){
int ans=-inf;
if(i){
ans=max(ans,dp[i-1][j][used][bal]+a[i][j]);
if(bal) ans=max(ans,dp[i-1][j][used][bal-1]);
int sum=0;
int it=0;
for(int cntuse=1;cntuse<=k&&cntuse<=tot;cntuse++){
sum+=b[it++];
ans=max(ans,dp[i-1][j][used-cntuse][bal]+sum+a[i][j]);
if(bal) ans=max(ans,dp[i-1][j][used-cntuse][bal-1]+sum);
}
}
if(j){
ans=max(ans,dp[i][j-1][used][bal]+a[i][j]);
if(bal) ans=max(ans,dp[i][j-1][used][bal-1]);
}
dp[i][j][used][bal]=ans;
}
}
}
}
int ans=0;
for(int i=0;i<=k;i++){
ans=max(ans,dp[n-1][m-1][i][i]);
}
cout<<ans<<endl;
}
return 0;
}