「广州集训 Day1」道路 - 期望+最长路

题目大意

我们看见了一个由m行n列的1*1的格子组成的矩阵，每个格子（I,j）有对应的高度h[i][j]和初始的一个非负权值v[i][j].我们可以随便选择一个格子作为起点，然后在接下来的每一步当中，我们能且只能到达与当前格子有边相邻的四个格子中的高度不超过当前格子高度的格子，每当我们到达一个新格子（包括一开始选择的初始格子），我们就能得到该格子的权值分，然后该格子的权值就会等概率变成不比当前的权值大的一个非负权值。每一个格子在满足前面条件情况下，可以走任意多次。
我们希望得到一个最大的期望权值和路径，并给出这个最大的期望权值和。

---

题目分析

权值变化一看就不可做，说明这个权值变化是很特殊的，说不定有什么性质。

化简数列

设$f(i)$为价值为$i$的格子走趋近于无穷次可以得到的期望。
题目说可以等概率的变成$j$的价值，那么可以变成自己的子问题解决。

$$f(i)=\sum_{j=0}^i\frac{f(j)+i}{i+1}$$

化简一下得：

$$f(i)=i+\sum_{j=0}^i\frac{f(j)}{i+1}$$

发现这个式子左右两边都含有$f(i)$，将右边的$f(i)$移项。

$$\frac{i}{i+1}f(i)=i+\sum_{j=0}^{i-1}\frac{f(j)}{i+1}$$

因此

$$f(i)=i+1+\sum_{j=0}^{i-1}\frac{f(j)}i$$

然后我就敲了这样一段代码：

double f[105];
int main() {
	f[0]=0;
	for(int i=1; i<=10; i++) {
		f[i]=i+1;
		for(int j=0; j<i; j++)f[i]+=f[j]/i;
		cout<<f[i]<<endl;
	}
	return 0;
}

发现规律：$f(i)=2i$。

怎么证明呢？
尝试去分母：

$$if(i)=i(i+1)+\sum_{j=0}^{i-1}f(j)$$

再来个$i-1$的式子

$$(i-1)f(i-1)=(i-1)i+\sum_{j=0}^{i-2}f(j)$$

两式相减得：

$$if(i)-(i-1)f(i-1)=2i+f(i-1)$$

化简得到：

$$f(i)-f(i-1)=2$$

证毕。

算法步骤

有了上述式子后，我们就可以做这道题了。
因为高度相同的块可以重复无限走，那么我们可以将高度相同的块缩成一个点，然后令其权值为权值总和$\times 2$。
然后跑一次最长路即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=1005;
const int Dirx[]= {0,1,-1,0,0},Diry[]= {0,0,0,1,-1};
int n,m,Belong[maxn][maxn],BCC=0,Size[maxn*maxn],h[maxn][maxn],InDegree[maxn*maxn];
map<int,map<int,int> >Hash;
vector<int>edges[maxn*maxn];
LL val[maxn*maxn],v[maxn][maxn],f[maxn*maxn],ans=0;
void Bfs(int sx,int sy) {
	queue<pair<int,int> >Q;
	Q.push(make_pair(sx,sy));
	Belong[sx][sy]=BCC;
	Size[BCC]=1;
	val[BCC]=v[sx][sy];
	while(!Q.empty()) {
		int x=Q.front().first,y=Q.front().second;
		Q.pop();
		for(int i=1; i<=4; i++) {
			int Nextx=x+Dirx[i],Nexty=y+Diry[i];
			if(Nextx<1||Nextx>n||Nexty<1||Nexty>m||h[x][y]!=h[Nextx][Nexty]||Belong[Nextx][Nexty])continue;
			Size[BCC]++;
			val[BCC]+=v[Nextx][Nexty];
			Belong[Nextx][Nexty]=BCC;
			Q.push(make_pair(Nextx,Nexty));
		}
	}
	if(Size[BCC]>1)val[BCC]*=2;
}
void AddEdge(int x,int y) {
	if(Hash.count(x)&&Hash[x].count(y))return;
	Hash[x][y]=1;
	edges[x].push_back(y);
	InDegree[y]++;
}
void Top_Sort() {
	queue<int>Q;
	for(int i=1; i<=BCC; i++)
		if(!InDegree[i]) {
			Q.push(i);
			f[i]=val[i];
			ans=max(ans,f[i]);
		}
	while(!Q.empty()) {
		int Now=Q.front();
		Q.pop();
		for(int& Next:edges[Now]) {
			f[Next]=max(f[Next],f[Now]+val[Next]);
			ans=max(ans,f[Next]);
			InDegree[Next]--;
			if(!InDegree[Next])Q.push(Next);
		}
	}
}
int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			h[i][j]=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			v[i][j]=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			if(!Belong[i][j]) {
				BCC++;
				Bfs(i,j);
			}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			for(int k=1; k<=4; k++) {
				int x=i+Dirx[k],y=j+Diry[k];
				if(x<1||x>n||y<1||y>m||h[i][j]<=h[x][y])continue;
				AddEdge(Belong[i][j],Belong[x][y]);
			}
	Top_Sort();
	printf("%lld\n",ans);
	return 0;
}