链接：https://ac.nowcoder.com/acm/contest/4090/C
来源：牛客网

 

 

 

 

 

示例1

输入

复制 
3 3 2
101 1 102
1 202 1
100 8 100

输出

复制 
414

备注:

 

 思路

　　通过二进制来枚举选哪几行几列的情况，维护最大的ans

 

CODE : 参考雨巨

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 50;
 47 
 48 int a[maxn][maxn];
 49 int row[maxn], line[maxn];
 50 bool b[30];
 51 
 52 LL sum = 0;
 53 
 54 int _count(int x) {
 55     memset(b, 0, sizeof(b));
 56     int cnt = 0;
 57     int q = 1;
 58     while(x) {
 59         if (x&1) {
 60             cnt++;
 61             b[q] = 1;
 62         }
 63         x >>= 1;
 64         q++;
 65     }
 66     return cnt;
 67 }
 68 
 69 int main()
 70 {
 71     int n,m,k;
 72     
 73     scanf("%d %d %d",&n, &m, &k);
 74     for ( int i = 1; i <= n; ++i ) {
 75         for ( int j = 1; j <= m; ++j ) {
 76             scanf("%d",&a[i][j]);
 77             sum += 1ll * a[i][j];
 78             line[i] += a[i][j];
 79         }
 80     }
 81     if(k >= n && k >= m) {
 82         printf("%lld\n",sum);
 83         return 0;
 84     }
 85     k = min(k, min(n, m));
 86     LL ans = 0;
 87     int temp = (1 << n);
 88     sum = 0;
 89     for ( int i = 0; i < temp; ++i ) {
 90         int numline = _count(i);
 91         sum = 0;
 92         int numrow = k - numline;
 93         if(numrow > m || numrow < 0) {
 94             continue;
 95         }
 96         for ( int j = 1; j <= n; ++j ) {
 97             if(b[j]) {
 98                 //printf("line[%d]:%d\n",j, line[j]);
 99                 sum += line[j];
100             }
101         }
102         memset(row, 0, sizeof(row));
103         for ( int j = 1; j <= n; ++j ) {
104             for ( int k = 1; k <= m; ++k ) {
105                 if(!b[j]) {
106                     row[k] += a[j][k];
107                 }
108             }
109         }
110         sort(row + 1, row + m + 1, greater<int>() );
111         //printf("!sum:%d\n",sum);
112         for ( int j = 1; j <= numrow; ++j ) {
113             //printf("row[%d]:%d\n",j, row[j]);
114             sum += row[j];
115         }
116         //dbg(sum);
117         //printf("\n");
118         ans = max(ans, sum);
119     }
120     cout << ans << endl;
121     return 0;
122 }
View Code

 

 

 

#include  < bits/stdc++.h >
#define  dbg (x ) cout  << #x  <<  " = "  << x  << endl
#define  eps  1e - 8
#define  pi  acos (- 1.0 )

using  namespace  std ;
typedef  long  long LL ;

template < class  T > inline  void  read ( T  &res )
{
     char c ;T flag = 1 ;
     while ((c = getchar ())< ' 0 ' ||c > ' 9 ' ) if (c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
     while ((c = getchar ())>= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}

namespace   _buff   {
     const   size_t  BUFF  =   1   <<   19 ;
     char  ibuf [ BUFF ],   * ib  =  ibuf ,   * ie  =  ibuf ;
     char   getc ()   {
         if   ( ib  ==  ie )   {
            ib  =  ibuf ;
            ie  =  ibuf  +   fread ( ibuf ,   1 ,  BUFF ,  stdin );
         }
         return  ib  ==  ie  ?   - 1   :   * ib ++;
     }
}

int  qread ()  {
     using  namespace  _buff ;
     int ret  =  0 ;
     bool pos  =  true;
     char c  =  getc ();
     for  (;  (c  <  ' 0 '  || c  >  ' 9 ' )  && c  !=  ' - ' ; c  =  getc ())  {
         assert (~ c );
     }
     if  (c  ==  ' - ' )  {
        pos  =   false;
        c  =   getc ();
     }
     for  (; c  >=  ' 0 '  && c  <=  ' 9 ' ; c  =  getc ())  {
        ret  =   ( ret  <<   3 )   +   ( ret  <<   1 )   +   ( c  ^   48 );
     }
     return pos  ? ret  :  -ret ;
}

const  int maxn  =  50 ;

int a [maxn ][maxn ];
int row [maxn ], line [maxn ];
bool b [ 30 ];

LL sum  =  0 ;

int  _count ( int x )  {
     memset (b ,  0 ,  sizeof(b ));
     int cnt  =  0 ;
     int q  =  1 ;
     while (x )  {
         if   ( x & 1 )   {
            cnt ++;
            b [ q ]   =   1 ;
         }
        x  >>=   1 ;
        q ++;
     }
     return cnt ;
}

int  main ()
{
     int n ,m ,k ;
    
     scanf ( " %d %d %d " ,&n ,  &m ,  &k );
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         for   (   int  j  =   1 ;  j  <=  m ;   ++ j  )   {
             scanf ( " %d " ,&a [ i ][ j ]);
            sum  +=   1ll   *  a [ i ][ j ];
            line [ i ]   +=  a [ i ][ j ];
         }
     }
     if (k  >= n  && k  >= m )  {
         printf ( " %lld\n " , sum );
         return   0 ;
     }
    k  =  min (k ,  min (n , m ));
    LL ans  =  0 ;
     int temp  =  ( 1  << n );
    sum  =  0 ;
     for  (  int i  =  0 ; i  < temp ;  ++i  )  {
         int  numline  =   _count ( i );
        sum  =   0 ;
         int  numrow  =  k  -  numline ;
         if ( numrow  >  m  ||  numrow  <   0 )   {
             continue ;
         }
         for   (   int  j  =   1 ;  j  <=  n ;   ++ j  )   {
             if (b [ j ])   {
                //printf("line[%d]:%d\n",j, line[j]);
                sum  +=  line [ j ];
             }
         }
         memset ( row ,   0 ,   sizeof( row ));
         for   (   int  j  =   1 ;  j  <=  n ;   ++ j  )   {
             for   (   int  k  =   1 ;  k  <=  m ;   ++ k  )   {
                 if (!b [ j ])   {
                    row [ k ]   +=  a [ j ][ k ];
                 }
             }
         }
         sort ( row  +   1 ,  row  +  m  +   1 ,   greater < int >()   );
        //printf("!sum:%d\n",sum);
         for   (   int  j  =   1 ;  j  <=  numrow ;   ++ j  )   {
            //printf("row[%d]:%d\n",j, row[j]);
            sum  +=  row [ j ];
         }
        //dbg(sum);
        //printf("\n");
        ans  =   max ( ans ,  sum );
     }
    cout  << ans  << endl ;
     return  0 ;
}