动态规划

#include

<

iostream

>

#include

<

cstdio

>

#include

<

cstdlib

>

#include

<

cstring

>

using

namespace

std;

#define

maxv 305

#define

maxp 35

int

cost[maxp][maxv];

int

d[maxv][maxv];

int

village[maxv];

int

v, p;

int

main()

{

//

freopen("t.txt", "r", stdin);

scanf(

"

%d%d

"

,

&

v,

&

p);

for

(

int

i

=

1

; i

<=

v; i

++

)

scanf(

"

%d

"

,

&

village[i]);

memset(d,

0

,

sizeof

(d));

for

(

int

i

=

1

; i

<

v; i

++

)

for

(

int

j

=

i

+

1

; j

<=

v; j

++

)

d[i][j]

=

d[i][j

-

1

]

+

village[j]

-

village[(i

+

j)

/

2

];

memset(cost,

0

,

sizeof

(cost));

for

(

int

i

=

1

; i

<=

v; i

++

)

cost[

1

][i]

=

d[

1

][i];

for

(

int

i

=

2

; i

<=

p; i

++

)

for

(

int

j

=

i; j

<=

v; j

++

)

{

cost[i][j]

=

1000000000

;

for

(

int

r

=

j

-

1

; r

>=

i

-

1

; r

--

)

cost[i][j]

=

min(cost[i][j], cost[i

-

1

][r]

+

d[r

+

1

][j]);

}

printf(

"

%d\n

"

, cost[p][v]);

return

0

;

}