http://ddtcms.com/blog/archive/2013/2/4/69/jieba-fenci-suanfa-lijie/
[UVa10859 – Placing Lampposts]DP状态表示的转换。
该题给出N个点M条边的无向无环图,在尽量少的节点上放灯,使得所有边都被照亮,每个节点将照亮与它相连的边。在放灯数量最少的前提下要求被两盏灯同时照亮的的边数应尽量大。
该题难点在于如何同时做到放灯最少和被两栈等同时照亮的最大。
首先统一到 “求最小” 的问题中来,问题转化为:在放灯数x最少的情况下使得仅被一条个等照亮的边数c最小。
定义一个较大的数M,使其超过题目情况中 c 的和的上界,该题可定义为2000.
则把状态转换为使得 M * x + c 最小。
那么最后放灯数应该是 ans / M, 仅被一个灯照亮的边数为: ans % M
还是忍不住贴个代码。。
# include <cstdio> # include <cstring> # include <algorithm> # define rep(i, n) for (int i = 0; i < n; ++i ) using namespace std; const int M = 2000; int n, m; struct edge { int v, next; }e[2009]; int h[1003], tot; void add(int a, int b) { e[++tot].v = b; e[tot].next = h[a]; h[a] = tot; } bool v[2003]; int f[2003][2]; void dfs(int x, int fa) { int j; v[x] = true; f[x][0] = 0; f[x][1] = M; for (int i = h[x]; i; i = e[i].next) { j = e[i].v; if ( !v[j] ) dfs(j, x); if ( j == fa ) continue; f[x][1] += min(f[j][0] + 1, f[j][1]); f[x][0] += f[j][1] + 1; } } int main() { int t, a, b; scanf("%d", &t); while ( t-- ) { memset(h, 0, sizeof h); memset(v, false, sizeof v); tot = 0; scanf("%d%d", &n, &m); rep(i, m) { scanf("%d%d", &a, &b); add(a, b); add(b, a); } int ans = 0; rep(i, n) if ( !v[i] ) { dfs(i, -1); ans += min(f[i][0], f[i][1]); } printf("%d %d %d\n", ans/M, m - ans % M, ans % M); } return 0; }
二进制表示的集合 枚举子集 的快速方法。
令要 枚举子集 的集合为S ,每一个二进制位表示一个元素是否存在。
则可 for (int S0 = S; S0; S0 = (S0 – 1)&S )
证明:
(S0 – 1)&S必然是S的子集
因为是从最后一位开始减小,所以(S0 – 1)&S必然是最十进制数位上最靠近S0的S的自己。
故可以用(S0 – 1) & S 来生成下一个子集并得到所有S的子集。
约瑟夫环问题的递推方法
对于给出的n个人,每隔k个人退出一个,第一次退出第m个人的约瑟夫环:
首先考虑从0开始编号,从第k个开始退出的情况。
则第k人退出后,约瑟夫环变为了:给出 n – 1 个人,每隔 k 个人退出一个 新约瑟夫环问题。给新环重新编号,与旧环建立的映射为:
k+1 => 0
k+2 => 1
…
k – 1 => n-2
假设 n-1 个人的约瑟夫环退出的人的编号为 x , 那么该人在 n 个人的环中的编号应该是 (x + k) % n
设f[n]表示,有N个人的约瑟夫环问题,最后退出的人的编号,则由上可得到递推式:
f[n] = (f[n-1] + k) % n
那么一个人的约瑟夫环的人必然是赢家,且编号为0,即: f[1] = 0
接下来可以使用递推得到最后结果。
最后对于f[n], 因为我们考虑的是从编号为 k 的开始,而题目要求从第 m 个开始退出,则需要旋转一下。
答案为 f[n] + m +1 – k。。
# include <cstdio> int n, m, k; int f[10003]; int main() { while ( scanf("%d%d%d", &n, &k, &m) == 3, n ) { f[1] = 0; for (int i = 2; i <= n; ++i ) f[i] = (f[i-1] + k) % i; int ans = ( f[n] + m - k + 1) % n; if ( ans <= 0 ) ans += n; printf("%d\n", ans); } return 0; }
公告0w0..
即日起本博客将减少直至停止发布奇怪的题解和奇怪的代码。
毕竟别人的博客都能找到的东西。