当前位置:首页 >> >>

NOI导刊坐标规则型动态规划.ppt_图文




Robots
n*m

:n<=100,m<=100


54

(1)

F(i,j)(1,1)(i,j)
F(i,j)=Max{f(i-1,j),f(i,j-1)}+c[i,j] C[i,j]=1(i,j)C[i,j]=0
1<=i<=n,1<=j<=m2 O(n*m)

(2)
G[i,j]f[i,j]
f(i,j) g(i,j)=g[i-1,j]*k+g[i,j-1]*L f[i-1,j]+c[i,j]=f[i,j]K=1K=0 f[i,j-1]+c[i,j]=f[i,j]L=1L=0
O(n*m)

NOIP2007
n*m aij
1. n m
2.
3. = *2iii 1
4. m




23 123 342
82 1
1*21+2*21=6 2
2*22+3*22=20 33*23+4*23=56
6+20+56=82


60%1<=n, m<=30 1016
100%1<=n, m<=80 0<=aij<=1000
1*21+2*21=6 2*22+3*22=20 3*23+4*23=56
1*21+2*22+3*23=
2*21+3*22+4*23


n f[i,j]i-j f[i,j]=max{f[i+1,j]+w*a[i] , f[i,j-1]+w*a[j]} w=w+w,w*2 max{f[i,i]+w*a[i]i=1..m}

(NOIP2008)
(1,1) (m,n)
0-100


1<=m,n<=50



111M,N. 1M,N 11.

12





(1,1)(M,N)
f(i1,j1,i2,j2)1(i1,j1)2(i2,j2)

f (i1 1, j1,i2 1, j2 )

f

(i1,

j1, i2 ,

j2

)



max

f f

(i1 (i1

, j1 1, 1, j1,

i2 i2

,j12,j12 ))



C[i1,

j1 ]



C[i2 ,

j2

]

f (i1, j1 1,i2, j2 1)

(i1,j1)<> (i2,j2) 1<=i1, i2<=M, 1<=j1 , j2<=N O(N2M2)

2

M+N

F(k,i1,i2)K1 i1,2i2

j1=K-i1, j2=K-i2 ,

f (k 1,i1,i2 )

f

(k,

i1,

i2

)



max


f f

(k (k

1, 1,

i1 1,i2 ) i1,i2 1)









C[i1

,

k



i1

]



C[i2

,

k



i2

]



i1<>i2

f (k 1,i1 1,i2 1)

1<=i1, i2<=M,1<=k<=N+M O((N+M)*M2)


SERKOI"" W
H 8-308 /

:W1~99H1 ~ 100 4 01


43 15 23 34 5+3+4=12




1 5





W*H

C[i,j]iji

F(i,j)ij

f (i 1, j 2)

f

(i,

j)



max

f f

(i (i

1, 1,

j 1) j)





c[i,

j]



f

(i

1,

j

1)



f (i 1, j 2)

0<=i<=T,1<=j<=W,5 O(5WT)


n

n100


(i,j)F(i,j)
F(i,j)=MIN{F(i-1,j-1),F(i-1,j+1)} +1
C[i-1,j]=`-'


(i,j)G(i,j)
G(i,j)=MIN{G(i+1,j-1),G(i+1,j+1)} +1
C[i+1,j]=`-'


F(i,j)G(i,j) 1<=i<=n,1<=j<=2n-1 O(N2) W +++...+2W-1=W2


for i:=1 to n do{} for j:=i to 2*n-i do if (c[i,j]='-')and(i mod 2=j mod 2) then{ } begin if c[i-1,j]<>'-' then f[i,j]:=1 else f[i,j]:=min(f[i-1,j-1],f[i-1,j+1])+1;{ } if f[i,j]>ans then ans:=f[i,j]; end; {}



F(i,j)=Max{f(i-1,k)}+k


更多相关标签: