dfs wa了大佬们帮帮我
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x,y) memset(x,y,sizeof(x)) #define Maxn 10005 #define P pair<int,int> using namespace std; int k, q; ll ans = 0; ll temp; int n, m; int vis[50]; int vis1[50]; int mp[50][50]; int mp1[50][50]; int mp2[50][50]; void dfs(int x) { if (x == min(k, q)) ans = max(ans, temp); else if (x > min(k, q)) return; else { for (int i = 0; i < n + m; i++) { if (i < n) { if (!vis[i]) { vis[i] = 1; int temp1 = temp; for (int j = 0; j < m; j++) { temp += mp[i][j]; mp1[i][j] = mp[i][j]; mp[i][j] = 0; } dfs(x + 1); vis[i] = 0; for (int j = 0; j < m; j++) { mp[i][j] = mp1[i][j]; temp -= mp[i][j]; } } } else { if (!vis1[i-n]) { vis1[i-n] = 1; for (int j = 0; j < m; j++) { temp += mp[j][i-n]; mp2[j][i - n] = mp[j][i - n]; mp[j][i-n] = 0; } dfs(x + 1); vis1[i-n] = 0; for (int j = 0; j < m; j++) { mp[j][i-n] = mp2[j][i-n]; temp -= mp[j][i-n]; } } } } } } int main() { cin >> n >> m >> k; q = min(n, m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> mp[i][j]; dfs(0); cout << ans << endl; }
全部评论
(2) 回帖