/*///题解写的很认真,如果您觉得还行的话可以顶一下或者评论一下吗?思路:这题复杂在要取前k大的结果,如果只是取最大情况下的金币和,直接动态规划递归就可以,可是前k大并不能找出什么公式,所以在二元数组的基础上再并上一个vector首先:初始化最左边和最上边(动态规划的边缘)其次:找出关系,每个格的金币只可能来自上边或者右边(动态规划的状态方程)然后:我们要找的是前k大金币总和而不是前1大,所以准备vector存更多情况然后:每次处理时,当前格子除了拿上自己的金币外,还要接受前面或者上边送来        的一袋袋金币这些金币,这些袋子有大有小,尽可能挑出前k大的袋子(如果没有        k那么多就全部挑出来),然后当前格子最多接受k+k袋金币(上面的k和左边的k)        接受时边接受边排序,那么下次当前格子附近的格子要调用这个格子的金币袋子        情况时找出前k大即可最后:f[m][n]这个最右下角的格子可能积累了一堆金币,从后往前(从大到小)挑出        k个袋子即可*///一个学长(栋神)出的题#include
     
      #define ll long longusing namespace std;const ll maxn=100;vector
      
       f[maxn][maxn];//f向量用来存每个位置前k大的总金币ll a[maxn][maxn];//a数组用来存入数据int main(){///输入环节    ll m,n,k;    cin>>m>>n>>k;    for(ll i=1;i<=m;i++)        for(ll j=1;j<=n;j++)            scanf("%lld",&a[i][j]);//输入金币情况///处理环节    f[1][1].push_back(a[1][1]);        //先向f向量中添加初始金币        //同样的,接下来两个for分别初始化向量左边和上面两个边界的金币数    for(ll i=2;i<=m;i++)        f[i][1].push_back(a[i][1]+(f[i-1][1])[0]);    for(ll i=2;i<=n;i++)        f[1][i].push_back(a[1][i]+(f[1][i-1])[0]);        //因为到最左竖和最上横分别只有一条路径,所以很好处理        ///接下来的向量f[i][j]会一直保持从小到大的排列顺序    for(ll i=2;i<=m;i++)        for(ll j=2;j<=n;j++)//两个for循环遍历剩下情况        {            //对f[i][j]的上面那格分析            if(k<=f[i-1][j].size())//如果要求的k比现在有的元素少                //即如果k比当前vector内元素数目小的情况            for(ll x=f[i-1][j].size()-1;x>=f[i-1][j].size()-k;x--)            {
    //从f[i-1][j]从后往前挑出k个数(也就是最大的k个数),分别加上a[i][j],塞入f[i][j]中                //这让f[i][j]增加了新的元素,但f[i][j]依然是从小到大排序(为后面服务)                (f[i][j]).insert(upper_bound(f[i][j].begin(),f[i][j].end(),(f[i-1][j])[x]+a[i][j]),(f[i-1][j])[x]+a[i][j]);            }            else//如果vector内元素数目小,还不够k多的情况            for(ll x=f[i-1][j].size()-1;x>=0;x--)            {
    //同上                (f[i][j]).insert(upper_bound(f[i][j].begin(),f[i][j].end(),(f[i-1][j])[x]+a[i][j]),(f[i-1][j])[x]+a[i][j]);            }            //对f[i][j]的左边那格分析            ///第一个if else是配套的,只执行一个,这里又是一套if else,只执行一个            //那么每次循环就处理一次上方,处理一次左边            if(k<=f[i][j-1].size())//类似于上面,不再叙述            for(ll x=f[i][j-1].size()-1;x>=f[i][j-1].size()-k;x--)            {                f[i][j].insert(upper_bound(f[i][j].begin(),f[i][j].end(),(f[i][j-1])[x]+a[i][j]),(f[i][j-1])[x]+a[i][j]);            }            else            for(ll x=f[i][j-1].size()-1;x>=0;x--)            {                f[i][j].insert(upper_bound(f[i][j].begin(),f[i][j].end(),(f[i][j-1])[x]+a[i][j]),(f[i][j-1])[x]+a[i][j]);            }        }    for(ll i=f[m][n].size()-1;i>=f[m][n].size()-k;i--)        printf("%lld ",(f[m][n])[i]);        //从后往前数k个数,分别输出(即在f[m][n]找出最大的k个数)}