51nod1625(枚举&贪心)

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1625

题意：中文题诶～

思路：枚举+贪心

一开始写的行和列同时枚举，写的时候就担心可能行和列会相互影响，提交结果证明我的担心是对的；

注意到1 <= n <= 10, 1 <= m <= 200，n很小，那么所有行的状态不超过1024种，所以可以枚举所有行的状态，对于每一种行的状态下再对列贪心。。

枚举行的所有状态可以用dfs。。

代码：

 1 #include <iostream>
 2 #include <string.h>
 3 #define ll long long
 4 using namespace std;
 5 
 6 const int MAXN=11;
 7 ll a[MAXN][MAXN*20], b[MAXN][MAXN*20], vis[MAXN], ans=0, m, n, x, k;
 8 
 9 ll get_ans(void){
10     ll ans=0;
11     for(int i=0; i<n; i++){
12         for(int j=0; j<m; j++){
13             ans+=b[i][j];
14         }
15     }
16     return ans;
17 }
18 
19 void solve(void){
20     int num=k;
21     memcpy(b, a, sizeof(a));
22     for(int i=0; i<n; i++){
23         if(vis[i]&&num>0){
24             num--;
25             for(int j=0; j<m; j++){
26                 b[i][j]=x;
27             }
28         }
29     }
30     while(num){
31         ll fj=-1, vj=0;
32         for(int j=0; j<m; j++){
33             ll cnt=0;
34             for(int i=0; i<n; i++){
35                 cnt+=x-b[i][j];
36             }
37             if(cnt>vj){
38                 vj=cnt;
39                 fj=j;
40             }
41         }
42         if(fj!=-1){
43             num--;
44             for(int i=0; i<n; i++){
45                 b[i][fj]=x;
46             }
47         }else break;
48     }
49     ans=max(ans, get_ans());
50 }
51 
52 void dfs(int x){
53     if(x>=n){
54         solve();
55         return;
56     }
57     vis[x]=1;
58     dfs(x+1);
59     vis[x]=0;
60     dfs(x+1);
61 }
62 
63 int main(void){
64     cin >> n >> m >> x >> k;
65     for(int i=0; i<n; i++){
66         for(int j=0; j<m; j++){
67             cin >> a[i][j];
68         }
69     }
70     dfs(0);
71     cout << ans << endl;
72     return 0;
73 }

View Code