本题传送门
解题思路
配合上一篇随笔的值传递，这题就是很讷的dfs函数。我这里是把所有的情况都存到了ans数组里，当然也可以用个全局变量mx来维护，最后输出mx就可以了
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int w[10][10];
vector<int> ans;
int n,m;
void dfs(int i,int j,int cur,int cnt)
{if(i > n || j > m ) return ;if(i == n && j == m) {if(cnt == 0) return ;double ave = cur / cnt;if( w[i][j] >= ave ) ans.push_back(cur + w[i][j]);else ans.push_back(cur);return ;}if(cur == 0){dfs(i + 1 , j , cur + w[i][j] , cnt + 1);dfs(i+1,j,cur,cnt);dfs(i , j + 1 , cur + w[i][j] , cnt + 1);dfs(i,j + 1,cur,cnt);}else{double ave = cur / cnt;if( w[i][j] >= ave){dfs(i + 1 , j ,cur + w[i][j] , cnt + 1);dfs(i,j + 1 , cur + w[i][j], cnt + 1);}else{dfs(i + 1 , j ,cur , cnt );dfs(i,j + 1 , cur , cnt);}}
}int main()
{
// int n,m;cin>>n>>m;for(int i = 1 ; i <= n ; i ++){for(int j = 1; j <= m ; j++) cin>>w[i][j];}dfs(1,1,0,0);sort(ans.begin(),ans.end());
// cout<<ans.size()<<endl;cout<<ans[ans.size() - 1]<<endl;return 0;
}