分数规划

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

设价值函数为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

广义括号法表示插头状态

例题：神奇游乐园

#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=x*10+ch-'0', ch=getchar();
	return x*f;
}

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;
}