Description

我們看見了一個(gè)由 m 行 n 列的 1*1 的格子組成的矩陣,每個(gè)格子(I,j)有對應(yīng)的高度 h[i][j]和初始的一個(gè)非負(fù)權(quán)值 v[i][j].我們可以隨便選擇一個(gè)格子作為起點(diǎn),然后在接下來的每一步當(dāng)中,我們能且只能到達(dá)與當(dāng)前格子有邊相鄰的四個(gè)格子中的高度不超過當(dāng)前格子高度的格子,每當(dāng)我們到達(dá)一個(gè)新格子(包括一開始選擇的初始格子),我們就能得到該格子的權(quán)值分,然后該格子的權(quán)值就會(huì)等概率變成不比當(dāng)前的權(quán)值大的一個(gè)非負(fù)權(quán)值。每一個(gè)格子在滿足前面條件情況下,可以走任意多次。我們希望得到一個(gè)最大的期望權(quán)值和路徑,并給出這個(gè)最大的期望權(quán)值和。

Input
第一行兩個(gè)正整數(shù)表示 m,n。
接下來的 m 行,每行 n 個(gè)正整數(shù),表示 h[i][j].
接下來的 m 行,每行 n 個(gè)非負(fù)整數(shù),表示 v[i][j].

Output
一行一個(gè)實(shí)數(shù),表示所求的最大期望權(quán)值和。保留零位小數(shù)。

Sample Input
1 3
1 2 1
1 2 3

Sample Output
5

Data Range
對于 30%的數(shù)據(jù),保證 n,m 不超過 100.
對于另外 20%的數(shù)據(jù),保證不存在相同的高度的格子。
對于 100%的數(shù)據(jù),保證 n,m 不超過 1000.所有權(quán)值與高度不超過 10^9.

Solution

對于高度相同的點(diǎn)可以重復(fù)來回走，把他們整體看成一個(gè)點(diǎn)，權(quán)值為v，每走完一次，他的權(quán)值變成[0,v]內(nèi)的一個(gè)值的概率一樣，那么期望的平均值為0.5v。每走一次，v'=0.5v，那么看成一個(gè)等比數(shù)列{v_i}，其中v1=v,v_i=0.5v_i-1,那么記等差數(shù)列前i項(xiàng)和為Si，當(dāng)i→+∞時(shí)，Si→2v（形象理解：一個(gè)餅每次切1/2，最后切到無限小;嚴(yán)謹(jǐn)推理：等比數(shù)列求和公式，在次不做贅述）

那么對于相同高度的點(diǎn)，縮成一個(gè)點(diǎn)，如果縮點(diǎn)前的點(diǎn)數(shù)>1，最后權(quán)值×2，最后對于每個(gè)縮的點(diǎn)跑一邊最長路即可(SPFA/DP)

要注意縮點(diǎn)BFS的寫法，不要隊(duì)列彈出時(shí)再記錄，加入隊(duì)列前就記錄，否則可能會(huì)WA

Code

?

1 #include<set> 2 #include<map> 3 #include<queue> 4 #include<stack> 5 #include<cstdio> 6 #include<cstring> 7 #include<iostream> 8 #include<algorithm> 9 #define inf (1<<30) 10 #define ll long long 11 #define RG register int 12 #define rep(i,a,b) for(RG i=a;i<=b;i++) 13 #define per(i,a,b) for(RG i=a;i>=b;i--) 14 #define maxn 1005 15 #define add(x,y) e[++cnt].v=y,e[cnt].next=head[x],head[x]=cnt 16 using namespace std; 17 typedef pair<int,int> pir; 18 int n,m,id,cnt; 19 int h[maxn][maxn],val[maxn][maxn],head[maxn*maxn]; 20 int rec[maxn][maxn]; 21 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 22 ll ans,V[maxn*maxn],f[maxn*maxn]; 23 struct E{ 24 int v,next; 25 }e[4000005]; 26 inline int read() 27 { 28 int x=0,f=1;char c=getchar(); 29 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 30 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 31 return x*f; 32 } 33 34 void DO(int x,int y) 35 { 36 ++id;int num=0; 37 queue<pir> que; 38 que.push((pir){x,y}); 39 pir u;int tx,ty; 40 while(!que.empty()) 41 { 42 u=que.front();que.pop(),++num; 43 rec[u.first][u.second]=id,V[id]+=val[u.first][u.second]; 44 rep(i,0,3) 45 { 46 tx=u.first+dir[i][0],ty=u.second+dir[i][1]; 47 if(tx<1||tx>n||ty<1||ty>m) continue; 48 if(rec[tx][ty]) continue; 49 if(h[tx][ty]!=h[u.first][u.second]) continue; 50 que.push((pir){tx,ty}); 51 } 52 } 53 if(num>1) V[id]<<=1; 54 } 55 56 ll LongPath(int u) 57 { 58 if(f[u]!=-1) return f[u]; 59 f[u]=0; 60 for(int i=head[u];i;i=e[i].next) 61 { 62 f[u]=max(f[u],LongPath(e[i].v)); 63 } 64 f[u]+=V[u]; 65 return f[u]; 66 } 67 68 int main() 69 { 70 freopen("road.in","r",stdin); 71 freopen("road.out","w",stdout); 72 n=read(),m=read(); 73 rep(i,1,n)rep(j,1,m) h[i][j]=read(); 74 rep(i,1,n)rep(j,1,m) val[i][j]=read(); 75 rep(i,1,n)rep(j,1,m) if(!rec[i][j]) DO(i,j); 76 int tx,ty; 77 rep(x,1,n)rep(y,1,m)rep(i,0,3) 78 { 79 tx=x+dir[i][0],ty=y+dir[i][1]; 80 if(tx<1||tx>n||ty<1||ty>m||h[tx][ty]>=h[x][y]) continue; 81 add(rec[x][y],rec[tx][ty]); 82 } 83 memset(f,-1,sizeof(f)); 84 rep(i,1,id) ans=max(ans,LongPath(i)); 85 cout<<ans; 86 return 0; 87 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/ibilllee/p/7798404.html

總結(jié)

以上是生活随笔為你收集整理的道路 [NOIP模拟]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。