BZOJ 1065 奥运物流

Link

做了大概一年的样子

Solution

因为任何站都可以到达$1$，所以这个图的形态一定是一个包含$1$的环上挂着很多树。 考虑环， $V_1=C_1+kV_3$ $V_2=C_2+kV_1$ $V_3=C_3+kV_2$ 带进去最后得到 $V_1-k^3V_1=C_1+kC_2+k^2C_3$, 可以看出每个点对答案的贡献与到$1$的距离成正相关，且$V_1$的值是和环的大小有关的。所以通过枚举修改环上点的后继为$1$，就可以得到确定环的大小，并且把这个图转化成一棵树，可以进行DP了（在建图的时候直接忽略$1$的后继，因为忽略了才是树，而且从上式可以看出忽略也没影响）。 然后就转化成一个树上的问题： 可以修改一个点的后继为$1$，使得$\sum k^{dist(1,i)}c_i$最大。 然后就开始高能了。 设计状态$f[i][j]$表示在以$i$为根的子树中修改$j$次，子树中的点对答案的最大贡献。 假如说现在要修改一个点的后继为$1$，有如下的情况：

1. 其子孙节点都没有改过
2. 其子孙节点有一个已经改到了1

明显对答案的影响是不一样的。这个状态没法转移。 于是$f[i][j][S]$表示在以$i$为根的子树中修改$j$次，其子孙节点的修改状态为$S$，子树中的点对答案的最大贡献。 发现这个问题的特点：当前状态的转移方法会对之后的状态的转移产生影响，而将当前状态的转移方法进行状压又不现实。 于是观察答案的性质：每个点对答案的贡献是$k^{dist(1,i)}c_i$，也就是说，只要$dist(1,i)$知道了，这个点对答案的贡献就可以算了。所以就考虑把状态加上一维:$f[i][j][d]$表示在以$i$为根的子树中修改$j$次，$dist(1,i)==d$的情况下，子树中的点对答案的最大贡献。 这样以来，每个点对答案的影响就可以独立统计了，也就解决了当前转移对后面状态转移产生影响的问题。 现在考虑如何转移$f[i][j][d]$(我做的时候把不合法的状态都设置了$-\infty$..) 首先定义$1$的深度$dep=0$ 对于$dep>1$的点，有两种选择：修改自己和不修改自己 如果修改自己，那子节点如果不修改，深度就是$2$，子节点如果修改，深度就是$1$； 如果不修改自己，子节点如果不修改，深度就是$dep+1$，如果修改，深度就是$1$。 所以

$f[i][j][d]=max \left\{ \begin{aligned} max\{\sum max\{f[son_t][k_t][d+1],f[son_t][k_t][1]\}|,\sum k_t==j\},d>1\\ max\{\sum max\{f[son_t][k_t][1],f[son_t][k_t][2]\}|,\sum k_t==j-1\},d==1\\ \end{aligned}\right.$

然后$dep==1$和$==0$也类似，就可做了。

初始的合法状态

以下纯属一个蒟蒻的自言自语 当$dep> 1$， 对于自己不修改的情况 $f[pos][0][dep]$肯定是合法的，置为$0$。 当在这棵子树中花费为$0$的时候，任意的$f[pos][0][d],d\le dep$都是合法的（祖先可能被修改）。 而对于自己有修改的情况，只需要把$f[pos][1][1]$置为$0$即可。 如果正向推不出来，可以反过来思考： 对于可能出现的每种合法转移，都必须能够沿着它的转移路线走到一个$0$。 对于自己不修改的情况，对于不同的$d$，$f[pos][][d]$的转移是互相独立的，所以在每种$d$上都需要有一个$0$。 对于自己有修改的情况，最终追溯到最优的一定是先用1次修改来把自己接到$1$上。 $\uparrow$其实这么做完全是作茧自缚，网上遍地是全都置$0$，在转移的时候走合法路径的代码。。

多重背包的滚动数组

有$N$种物品和一个容量为$V$的背包。第$i$种物品最多有$M_i$件可用，每件耗费的空间是$C_i$，价值是$W_i$。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

for(int i=1;i<=n;i++)
	for(int v=0;v<=V;v++)
    	for(int k=0;k*c[i]<=v && k<=cnt[i];k++)
        	chkmx(f[i][v],f[i-1][v-k*c[i]]+k*w[i]);

对于$01$背包和完全背包，可以使用滚动数组优化空间复杂度。

for(int i=1;i<=n;i++)
	for(int v=V;v>=c[i];v--)
    //for(int v=c[i];v<=V;v++)
    	chkmx(f[v],f[v-c[i]]+w[i]);

而对于多重背包，使用滚动数组必须要保证：对于同一个体积$v$，不会同时被$k_1$和$k_2$个相同的物品同时优化。 即，不能在一个体积的背包里先装上$k_1$个$A$，然后又装上$k_2$个$A$。 实现的方法是

for(int i=1;i<=n;i++)
	for(int v=V;~v;v--)
    	for(int k=0;k*c[i]<=v && k<=cnt[i];k++)
        	chkmx(f[v],f[v-k*c[i]]+k*w[i]);

对于一般的多重背包，第三层循环的枚举顺序应该可以倒过来(我没想出反例的样子？) 但是对于这道题目就不行了。 因为这个题目在$k==0$的时候也可能会对答案产生贡献，如果从大到小枚举，就会让答案多加了$f[u][0][d+1/1]$(不要问我怎么知道的) 所以不管怎样写成从小到大的还是保险一些。(也许这样写也有坑点？)

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define getf(x) scanf("%lf",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100;
const double INF=1e10;
using std::vector;
using std::max;

vector<int> son[MAXN];
double c[MAXN],f[MAXN][MAXN][MAXN],pw[MAXN];int m;

void DP(int pos,int dep)
{
	#define foreach(it,x) for(vector<int>::iterator it=x.begin();it!=x.end();++it)
	for(int j=0;j<=m;j++)
		for(int d=0;d<=dep;d++)
			f[pos][j][d]=-INF;//*(j!=0);//-INF;
	f[pos][0][dep]=0;
	foreach(it,son[pos]) DP(*it,dep+1);
	if(dep>1)
	{
		//每个d是一个独立的背包
		f[pos][1][1]=0;
		for(int d=2;d<dep;d++) f[pos][0][d]=0;
		//改自己
		foreach(it,son[pos])
		{
			int u=*it;
			for(int v=m-1;~v;v--)
				for(int i=v;~i;i--)
					chkmx(f[pos][v+1][1],f[pos][i+1][1]+max(f[u][v-i][1],f[u][v-i][2]));
		}
		//不改自己
		for(int d=2;d<=dep;++d)
			foreach(it,son[pos])
			{
				int u=*it;
				for(int v=m;~v;v--)
					for(int i=v;~i;i--)
						chkmx(f[pos][v][d],f[pos][i][d]+max(f[u][v-i][1],f[u][v-i][d+1]));
			}
		for(int d=1;d<=dep;d++)
			for(int v=m;~v;v--)
				f[pos][v][d]+=c[pos]*pw[d];
	}
	else if(dep==1)
	{
		foreach(it,son[pos])
		{
			int u=*it;
			for(int v=m;~v;v--)
				for(int i=v;~i;i--)
					chkmx(f[pos][v][1],f[pos][i][1]+max(f[u][v-i][1],f[u][v-i][2]));
		}
		for(int v=m;~v;v--)
			f[pos][v][1]+=c[pos]*pw[1];
	}
	else
	{
		foreach(it,son[pos])
		{
			int u=*it;
			for(int v=m;~v;v--)
				for(int i=v;~i;i--)	
					chkmx(f[pos][v][0],f[pos][i][0]+f[u][v-i][1]);
		}
		for(int v=m;~v;v--)
			f[pos][v][0]+=c[pos]*pw[0];
	}
}
int main()
{
	static int succ[MAXN];
	int n;double K;
	get(n),get(m),getf(K);
	pw[0]=1;for(int i=1;i<=n;i++) pw[i]=pw[i-1]*K;
	for(int i=1;i<=n;i++) get(succ[i]);
	for(int i=1;i<=n;i++) getf(c[i]);
	double Ans=-INF;
	for(int brp=succ[1],cl=2;brp!=1;brp=succ[brp],cl++)
	{
		for(int i=1;i<=n;i++) son[i].clear();
		for(int i=2;i<=n;i++) 
			son[i==brp?1:succ[i]].push_back(i);
		DP(1,0);
		double res=-INF;
		for(int i=m-(succ[brp]!=1);~i;i--) chkmx(res,f[1][i][0]);
		chkmx(Ans,res/(1-pw[cl]));
	}
	printf("%.2lf\n",Ans);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */