hdu_1355

再来一题~~天道酬勤~~

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=11111;
int T,m,n,k,temp,sum;
int t[maxn];
int a[55][55];
struct pp
{
    int x,y,num;
    bool operator < (const pp&cmp) const
    {
        return num < cmp.num;
    }
}px;  
vector<pp>v;
int dpstart()
{
    sum=0;
    t[0]=1;
    for(int i=1;i<v.size();i++)     
    {
        t[i]=abs(v[i].y-v[i-1].y)+abs(v[i].x-v[i-1].x)+1;                                                         
    }
    for(int i=v.size()-1;i>=0;i--)
    {
        if(k-v[i].x-1>=0)
        {
            sum+=v[i].num;      
            k-=t[i];        
        }
        else
        {
            return sum;
        }      
    }
    return sum;
}
int main()
{
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        v.clear();
        cin>>m>>n>>k;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>a[i][j];
                if(a[i][j]!=0)
                {
                    px.num=a[i][j]; 
                    px.x=i; 
                    px.y=j;
                    v.push_back(px);
                }
            }      
        }
        sort(v.begin(),v.end());
        k-=v.back().x;
        cout<<dpstart()<<endl;
    }        
    return 0;
}