【规划】动态规划、分数规划、线性规划

NanoApe posted @ 2016年2月12日 12:36 in 蒟蒻不撕烤智熵何来 , 1465 阅读

分数规划

求一类最值规划类型的问题

设价值函数为v，代价函数为w，则收益函数为

$F(C)=\frac{\sum^{|C|} v(C_i)}{\sum^{|C|} w(C_i)}$

C为决策的集合

设 $Max[F(C)]=a$ ，变形一下，对于任意一个决策C，都满足

$a \ge \frac{\sum_i^{|C|}v(C_i)}{\sum_i^{|C|}w(C_i)}$

$\sum_i^{|C|}a*w(C_i)-v(C_i) \ge 0$

对于求最小值的分数规划问题，同理

斯坦纳树

$dp[i][state]$ 表示以 $i$ 为根，指定集合中的点的连通状态为 $state$ 的生成树的最小总权值

转移方程：

$dp[i][state]=min(dp[i][subset1]+dp[i][subset2], dp[j][state]+e[i][j])$

枚举 $state$ ，然后先处理前半部分转移，后半部分用SPFA转移

插头DP

广义括号法表示插头状态

例题：神奇游乐园

BZOJ1187
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113	`#include <cstdio>` `#include <algorithm>` `#include <queue>` `#include <cstring>` `#include <map>` `#include <vector>` `using` `namespace` `std;` `#define rep(i, l, r) for(int i=l; i<=r; i++)` `#define dow(i, l, r) for(int i=l; i>=r; i--)` `#define travel(x) for(edge p=fir[x]; p; p=p->n)` `#define clr(x,c) memset(x, c, sizeof(x))` `typedef` `pair<int,int> Pii;` `typedef` `long` `long` `ll;` `#define pb push_back` `#define mp make_pair` `#define all (x).begin(), (x).end()` `#define lowbit(x) (x&-x)` `#define l(x) Left[x]` `#define r(x) Right[x]` `#define inf 0x3fffffff` `#define maxn 109` `#define maxS 16389` `inline` `int` `read()` `{` `int` `x=0, f=1;` `char` `ch=getchar();` `while` `(ch<'0'` `\|\| ch>'9') {if` `(ch=='-') f=-1; ch=getchar();}` `while` `('0'<=ch && ch<='9') x=x10+ch-'0', ch=getchar();` `return` `xf;` `}` `int` `n, m, k[109][7], mx, A=-0x7fffffff;` `int` `f[109][7][maxS];` `bool` `b[109][7][maxS];` `int` `c[5], g[9], d[9], nw, q[9], top;` `inline` `void` `unzip(int` `S)` `{` `rep(i, 0, m) d[i]=S&3, S>>=2;` `nw=0; rep(i, 0, m)` `{` `if` `(d[i]==0) g[i]=0;` `if` `(d[i]==1) q[++top]=g[i]=++nw;` `if` `(d[i]==2) g[i]=q[top--];` `}` `}` `inline` `int` `zip(int` `op)` `{` `if` `(!op)` `{` `int` `now=0; clr(c,-1);` `rep(i, 0, m)` `if` `(!g[i]) d[i]=0;` `else` `if` `(c[g[i]]==-1) d[i]=1,c[g[i]]=i;` `else` `d[i]=2;` `dow(i, m, 0) now<<=2, now\|=d[i];` `return` `now;` `}` `if` `(g[op-1]==g[op])` `return` `nw!=1?-2:-1;` `int` `tmp=g[op]; rep(i, 0, m)` `if` `(g[i]==tmp) g[i]=g[op-1];` `g[op-1]=g[op]=0;` `int` `now=0; clr(c,-1);` `rep(i, 0, m)` `if` `(!g[i]) d[i]=0;` `else` `if` `(c[g[i]]==-1) d[i]=1,c[g[i]]=i;` `else` `d[i]=2;` `dow(i, m, 0) now<<=2, now\|=d[i];` `return` `now;` `}` `inline` `void` `update(int` `x,` `int` `y,` `int` `o,` `int` `v)` `{` `if` `(o==-1) A=max(A,v);` `if` `(o<0)` `return;` `if` `(y>m) x++, y=1, o<<=2;` `if` `(o>mx)` `return;` `if` `(!b[x][y][o]) b[x][y][o]=1, f[x][y][o]=v;` `else` `f[x][y][o]=max(f[x][y][o],v);` `}` `int` `main()` `{` `n=read(), m=read(); rep(i, 1, n) rep(j, 1, m) k[i][j]=read();` `f[1][1][0]=0; b[1][1][0]=true;` `mx=(1<<(2(m+1)))-1; rep(i, 1, n)` `{` `rep(j, 1, m)` `{` `rep(o, 0, mx)` `if` `(b[i][j][o])` `{` `unzip(o);` `if` `(!g[j-1] && !g[j])` `{` `g[j-1]=nw+1, g[j]=nw+1;` `update(i,j+1,zip(0),f[i][j][o]+k[i][j]);` `g[j-1]=0, g[j]=0;` `update(i,j+1,zip(0),f[i][j][o]);` `}` `if` `((!g[j-1] && g[j]) \|\| (g[j-1] && !g[j]))` `{` `swap(g[j-1], g[j]);` `update(i,j+1,zip(0),f[i][j][o]+k[i][j]);` `swap(g[j-1], g[j]);` `update(i,j+1,zip(0),f[i][j][o]+k[i][j]);` `}` `if` `(g[j-1] && g[j])` `update(i,j+1,zip(j),f[i][j][o]+k[i][j]);` `}` `}` `}` `printf("%d\n", A);` `return` `0;` `}`

NanoApe's Blog

既是咸鱼又是辣鸡

【规划】动态规划、分数规划、线性规划

分数规划

斯坦纳树

插头DP

NanoApe

计数器

分类

搜索

听听看？

最新留言

最新评论

链接

RSS