牛客练习赛58 矩阵消除游戏

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

示例1

输入

输出

复制

备注:

思路

　　通过二进制来枚举选哪几行几列的情况，维护最大的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
",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
",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
",sum);
112         for ( int j = 1; j <= numrow; ++j ) {
113             //printf("row[%d]:%d
",j, row[j]);
114             sum += row[j];
115         }
116         //dbg(sum);
117         //printf("
");
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
",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
",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
",sum);
        for ( int j = 1; j <= numrow; ++j ) {
            //printf("row[%d]:%d
",j, row[j]);
            sum += row[j];
        }
        //dbg(sum);
        //printf("
");
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}