首页 > 代码库 > UVALive 6088 Approximate Sorting 构造题
UVALive 6088 Approximate Sorting 构造题
题目链接:点击打开链接
题意:
给定一个n*n的01矩阵
我们跑一下样例==
4
0111
0000
0100
0110
0123
\|____
0|0111
1|0000
2|0100
3|0110
用0-n-1随便构造一个序列:
如:1230
我们计算1230的权值 :
int ans = 0;
对于个位0,我们查找第0行:0111,0前面的数有123, 则ans += a[0][1], ans+=a[0][2], ans+=a[0][3]
对于十位3,我们查找第3行:0110,3前面的数有12, ans+=a[3][1], ans+=a[3][2]
如此得到ans = 6
问:
构造一个这样的序列使得ans最小,若有多个这样的序列则输出序列字典序最小的。
#include <cstdio> #include <iostream> #include <string> #include <map> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int Inf = 1e9; typedef long long ll; const int N = 18; const int S = 1 << N; int d[S], one[S]; int w[N], n, mx; int out[N], dep; map<int, int> id; int dp(int s) { if (~d[s]) return d[s]; d[s] = Inf; int i, to, x = s; while (x>0) { to = (x&(x-1)) ^ x; i = id[to]; d[s] = min(d[s], dp(s^(1<<i)) + one[w[i]&s]); x = x^to; } return d[s]; } void dfs(int dep, int cur, int g) { if (dep == N) { one[cur] = g; } else { dfs(dep+1, cur*2+1, g+1); dfs(dep+1, cur*2, g); } } void path(int s) { if (s != 0) { for (int i = 0; i < n; ++i) if (s >> i & 1) { if (dp(s^(1 << i)) + one[w[i]&s] == dp(s) ) { out[dep++] = i; path(s^(1 <<i)); return ; } } } } char s[N]; void work() { memset(w, 0, sizeof w); for (int i = 0; i < n; ++i) { scanf("%s", s); for (int j = 0; j < n; ++j) if (s[j] == '1' && j != i) w[j] |= 1 << i; } mx = (1 << n) - 1; memset(d, -1, sizeof d); d[0] = 0; int ans = dp(mx); dep = 0; path(mx); for (int i = 0; i < dep; ++i) { if (i > 0) putchar(' '); printf("%d", out[i]); } puts(""); printf("%d\n", ans); } int main() { dfs(0, 0, 0); for (int i = 0; i < N; ++i) id[1 << i] = i; while (~scanf("%d", &n)) { if (0 == n) break; work(); } return 0; }
UVALive 6088 Approximate Sorting 构造题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。