繁凡的ACM编程竞赛模板集合

二、动态规划

∮ 1. 背包

1.【01背包】

按长度对字符串比较

strn

c

mp

字符串转换

strxfrm

字符与字符串查找

字符查找

mem

c

hr

字符查找

str

c

hr

字符串查找

str

c

spn

字符串查找

strp

b

rk

字符串查找

strspn

字符串查找

strstr

字符串分解

strtok

杂类函数

字符串设置

memset

错误字符串映射

strerror

求字符串长度

strlen

14

15

16

17

18

19

20

21

22

23

24

25

26

头文件

stdli

b

.

h

实用工具函数

:

本分类给出了一些函数无法按以上分类，但又是编程所必须要的。



字符串转换函数

字符串转换为整数

a

toi

字符串转换为长整数

a

tol

字符串转换为浮点数

strtod

字符串转换为长整数

strtol

字符串转换为无符号长整型

strtoul

伪随机序列产生函数

产生随机数

r

a

nd

设置随机函数的起动数值

sr

a

nd

存储管理函数

分配存储器

ca

llo

c

释放存储器

free

存储器分配

m

a

llo

c

重新分配存储器

re

a

llo

c

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

序号

库类别

头文件



1



错误处理

  

errno

.

h

2



字符处理

  

c

typhe

.

3



地区化

   

lo

ca

l

.

h

4



数学函数

  

m

a

th

.

h

5



信号处理

  

sign

a

l

.

h

6



输入输出

  

stdio

.

h

7



实用工具程序



stdli

b

.

h

8



字符串处理

 

string

.

h

1

2

3

4

5

6

7

8

9

10

11

16

繁凡的 ACM 模板

————————————————————————————————————————————————————————————————————————————

2.【完全背包】

3.【多人背包】

他们一共有 K 个人，每个人都会背一个包。这些包的容量是相同的，都是 V。可以装进背包里的一共有 N 种物品，每种物品都

有

给定的体积和价值。在 DD 看来，合理的背包安排方案是这样的：每个人背包里装的物品的总体积恰等于包的容量。

每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。任意两个人，他们包里的物品清单不能完全相同。

在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？

4.【分组背包】

#

in

c

lude

<

a

lgorithm

>

#

in

c

lude

<

c

stdio

>

int

T

,

n

,

i

,

j

,

v

[

110

],

w

[

110

],

f

[

1010

];

int

m

a

in

(){

 

s

ca

nf

("

%

d

%

d

",

&

T

,

&

n

);

 

for

(

i

=

1

;

i





n

;

i





)

s

ca

nf

("

%

d

%

d

",

&

v

[

i

],

&

w

[

i

]);

 

for

(

i

=

1

;

i





n

;

i





)

   

for

(

j

=

T

;

j





v

[

i

];

j





)

     

f

[

j

]

=

std





m

a

x

(

f

[

j

],

f

[

j

-

v

[

i

]]

+

w

[

i

]);

 

printf

("

%

d

",

f

[

T

]);

}

1

2

3

4

5

6

7

8

9

10

11

#

in

c

lude

<

b

its

/

std

c





.

h

>

using

n

a

mesp

ac

e

std

;

int

T

,

n

,

a

ns

,

a

[

105

],

dp

[

30005

];

int

m

a

in

(){

 

s

ca

nf

("

%

d

",

&

T

);

 

while

(

T





){

   

memset

(

dp

,-

127

,

sizeof

(

dp

));

   

s

ca

nf

("

%

d

",

&

n

);

dp

[

0

]

=

a

ns

=

0

;

   

for

(

int

i

=

1

;

i





n

;

i





)

s

ca

nf

("

%

d

",

&

a

[

i

]);

   

for

(

int

i

=

1

;

i





n

;

i





)

     

for

(

int

j

=

a

[

i

];

j





25000

;

j





)

       

dp

[

j

]

=

m

a

x

(

dp

[

j

],

dp

[

j

-

a

[

i

]]

+

1

);

   

for

(

int

i

=

1

;

i





n

;





i

)

a

ns

+=

dp

[

a

[

i

]]





1

;

   

printf

("

%

d

\

n

",

a

ns

);

 }

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

#

in

c

lude

<

a

lgorithm

>

#

in

c

lude

<

c

string

>

#

in

c

lude

<

c

stdio

>

int

a

ns

,

T

,

n

,

i

,

j

,

k

,

K

,

a

,

b

,

t

,

re

[

45

],

v

[

210

],

w

[

210

],

f

[

5010

][

45

];

int

m

a

in

(){

 

s

ca

nf

("

%

d

%

d

%

d

",

&

K

,

&

T

,

&

n

);

 

memset

(

f

,-

127

,

sizeof

(

f

));

f

[

0

][

1

]

=

0

;

 

for

(

i

=

1

;

i





n

;

i





)

s

ca

nf

("

%

d

%

d

",

&

v

[

i

],

&

w

[

i

]);

 

for

(

i

=

1

;

i





n

;

i





)

   

for

(

j

=

T

;

j





v

[

i

];

j





){

     

a

=

b

=

1

,

t

=

0

;

     

while

(

t





K

)

       

if

(

f

[

j

][

a

]





f

[

j

-

v

[

i

]][

b

]

+

w

[

i

])

re

[





t

]

=

f

[

j

][

a





];

       

else

re

[





t

]

=

f

[

j

-

v

[

i

]][

b





]

+

w

[

i

];

     

for

(

k

=

1

;

k





K

;

k





)

f

[

j

][

k

]

=

re

[

k

];

   }

 

for

(

i

=

1

;

i





K

;

i





)

a

ns

+=

f

[

T

][

i

];

 

printf

("

%

d

",

a

ns

);

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

#

in

c

lude

<

a

lgorithm

>

1

17

繁凡的 ACM 模板

————————————————————————————————————————————————————————————————————————————

5.【多重背包】

6.【混合背包】

#

in

c

lude

<

c

stdio

>

using

n

a

mesp

ac

e

std

;

int

T

,

n

,

i

,

j

,

a

[

65

],

s

,

t

,

r

1

,

r

2

,

r

[

65

][

3

],

v

[

65

],

w

[

65

],

f

[

32010

];

int

m

a

in

(){

 

s

ca

nf

("

%

d

%

d

",

&

T

,

&

n

);

 

v

[

0

]

=

0

xfffffff

;

 

for

(

i

=

1

;

i





n

;

i





){

   

s

ca

nf

("

%

d

%

d

%

d

",

&

v

[

i

],

&

s

,

&

a

[

i

]);

   

if

(

a

[

i

])

r

[

a

[

i

]][





r

[

a

[

i

]][

0

]]

=

i

;

w

[

i

]

=

v

[

i

]*

s

;

 }

 

for

(

i

=

1

;

i





n

;

i





)

   

for

(

j

=

T

;

j





v

[

i

]





(!

a

[

i

]);

j





){

     

t

=

j

-

v

[

i

],

r

1

=

r

[

i

][

1

],

r

2

=

r

[

i

][

2

];

     

f

[

j

]

=

m

a

x

(

f

[

j

],

f

[

t

]

+

w

[

i

]);

     

if

(

v

[

r

1

]





t

)

f

[

j

]

=

m

a

x

(

f

[

j

],

f

[

t

-

v

[

r

1

]]

+

w

[

i

]

+

w

[

r

1

]);

     

if

(

v

[

r

2

]





t

)

f

[

j

]

=

m

a

x

(

f

[

j

],

f

[

t

-

v

[

r

2

]]

+

w

[

i

]

+

w

[

r

2

]);

     

if

(

v

[

r

1

]

+

v

[

r

2

]





t

)

f

[

j

]

=

m

a

x

(

f

[

j

],

f

[

t

-

v

[

r

1

]-

v

[

r

2

]]

+

w

[

i

]

+

w

[

r

1

]

+

w

[

r

2

]);

   }

 

printf

("

%

d

",

f

[

T

]);

}

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

#

in

c

lude

<

a

lgorithm

>

#

in

c

lude

<

c

string

>

#

in

c

lude

<

c

stdio

>

#

define

R

e

register

int

using

n

a

mesp

ac

e

std

;

c

onst

int

N

=

103

,

M

=

4

e

4

+

3

;

int

n

,

m

,

x

,

y

,

z

,

V

,

a

ns

,

v

[

N

*

17

],

w

[

N

*

17

],

dp

[

M

];

inline

void

in

(

R

e

&

x

){

 

R

e

fu

=

0

;

x

=

0

;

c

h

a

r

c

h

=

get

c

h

a

r

();

 

while

(

c

h

<

'

0

'





c

h

>

'

9

')

fu

|

=

c

h





'-',

c

h

=

get

c

h

a

r

();

 

while

(

c

h





'

0

'





c

h





'

9

')

x

=

(

x





1

)

+

(

x





3

)

+

(

c

h

^

48

),

c

h

=

get

c

h

a

r

();

 

x

=

fu

?-

x

:

x

;

}

int

m

a

in

(){

 

in

(

m

),

in

(

V

);

 

memset

(

dp

,-

127

,

sizeof

(

dp

));

 

dp

[

0

]

=

0

;

 

while

(

m





){

   

in

(

x

),

in

(

y

),

in

(

z

);

R

e

p

=

1

;

   

while

(

z





p

)

v

[





n

]

=

y

*

p

,

w

[

n

]

=

x

*

p

,

z

-

=

p

,

p





=

1

;

   

if

(

z

)

v

[





n

]

=

y

*

z

,

w

[

n

]

=

x

*

z

;

 }

 

for

(

R

e

i

=

1

;

i





n

;





i

)

   

for

(

R

e

j

=

V

;

j





v

[

i

];



j

)

     

dp

[

j

]

=

m

a

x

(

dp

[

j

],

dp

[

j

-

v

[

i

]]

+

w

[

i

]);

 

for

(

R

e

i

=

0

;

i





V

;





i

)

a

ns

=

m

a

x

(

a

ns

,

dp

[

i

]);

 

printf

("

%

d

\

n

",

a

ns

);

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

#

in

c

lude

<

a

lgorithm

>

#

in

c

lude

<

c

stdio

>

using

n

a

mesp

ac

e

std

;

int

x

,

a

,

b

,

c

,

d

,

T

,

n

,

i

,

j

,

t

,

f

[

1010

],

v

[

100010

],

w

[

100010

];

int

m

a

in

(){

 

s

ca

nf

("

%

d

:

%

d

%

d

:

%

d

%

d

",

&

a

,

&

b

,

&

c

,

&

d

,

&

n

);

 

T

=

c

*

60

+

d

-

a

*

60

-

b

;

1

2

3

4

5

6

7

18

繁凡的 ACM 模板

————————————————————————————————————————————————————————————————————————————

7.【二维费用】

∮ 2. 树形DP

(1).【简单树形 DP】

 

for

(

i

=

1

;

i





n

;

i





){

   

s

ca

nf

("

%

d

%

d

%

d

",

&

a

,

&

b

,

&

c

);

   

if

(!

c

){

     

for

(

j

=

0

;

j

+

a





T

;

j





)

     

f

[

j

+

a

]

=

m

a

x

(

f

[

j

+

a

],

f

[

j

]

+

b

);

     

c

ontinue

;

   }

   

x

=

1

;

   

while

(

c





x

){

v

[





t

]

=

x

*

a

,

w

[

t

]

=

x

*

b

,

c

-

=

x

,

x





=

1

;}

   

v

[





t

]

=

c

*

a

,

w

[

t

]

=

c

*

b

;

 }

 

for

(

i

=

1

;

i





t

;

i





)

   

for

(

j

=

T

;

j





v

[

i

];

j





)

     

f

[

j

]

=

m

a

x

(

f

[

j

],

f

[

j

-

v

[

i

]]

+

w

[

i

]);

 

printf

("

%

d

",

f

[

T

]);

}

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

#

in

c

lude

<

a

lgorithm

>

#

in

c

lude

<

c

stdio

>

using

n

a

mesp

ac

e

std

;

int

tmp

,

T

1

,

T

2

,

x

,

y

,

n

,

i

,

j

,

k

,

v

1

[

105

],

v

2

[

105

],

w

[

105

],

dp

[

105

][

105

],

a

ns

[

105

][

105

];

int

m

a

in

(){

 

s

ca

nf

("

%

d

",

&

n

);

 

for

(

i

=

1

;

i





n

;

i





)

s

ca

nf

("

%

d

%

d

%

d

",

&

v

1

[

i

],

&

v

2

[

i

],

&

w

[

i

]);

 

s

ca

nf

("

%

d

%

d

",

&

T

1

,

&

T

2

);

 

for

(

i

=

1

;

i





n

;





i

)

   

for

(

j

=

T

1

;

j





v

1

[

i

];



j

)

     

for

(

k

=

T

2

;

k





v

2

[

i

];



k

)

       

if

(

dp

[

j

][

k

]

<

(

tmp

=

dp

[

j

-

v

1

[

i

]][

k

-

v

2

[

i

]]

+

1

)){

         

dp

[

j

][

k

]

=

tmp

;

         

a

ns

[

j

][

k

]

=

a

ns

[

j

-

v

1

[

i

]][

k

-

v

2

[

i

]]

+

w

[

i

];

       }

       

else

if

(

dp

[

j

][

k

]





tmp

)

a

ns

[

j

][

k

]

=

min

(

a

ns

[

j

][

k

],

a

ns

[

j

-

v

1

[

i

]][

k

-

v

2

[

i

]]

+

w

[

i

]);

 

printf

("

%

d

",

a

ns

[

T

1

][

T

2

]);

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

#

in

c

lude

<

a

lgorithm

>

#

in

c

lude

<

c

string

>

#

in

c

lude

<

c

stdio

>

#

define

R

register

int

using

n

a

mesp

ac

e

std

;

int

he

a

d

[

6010

],

a

,

b

,

t

,

i

,

j

,

n

,

f

[

6010

][

2

],

p

a

n

[

6010

];

stru

c

t

QAQ

{

int

to

;}

Q

[

6010

];

inline

void

a

dd

(

int

x

,

int

y

){

Q

[





t

].

to

=

y

,

Q

[

t

].

he

a

d

[

x

],

he

a

d

[

x

]

=

t

;}

inline

void

dfs

(

int

w

){

 

for

(

R

k

=

he

a

d

[

w

];

k

;

k

=

Q

[

k

].

   

int

to

=

Q

[

k

].

to

;

   

dfs

(

to

);

   

f

[

w

][

0

]

+=

m

a

x

(

f

[

to

][

0

],

f

[

to

][

1

]);

   

f

[

w

][

1

]

+=

f

[

to

][

0

];

 }

}

int

m

a

in

(){

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

19

繁凡的 ACM 模板

————————————————————————————————————————————————————————————————————————————

(2).【换根 DP】

每个奶牛居住在 N 个农场中的一个，这些农场由 N−1 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路 i 连接

农场

和，长度为。集会可以在 N 个农场中的任意一个举行。另外，每个牛棚中居住着只奶牛。

在选择集会的地点的时候，Bessie 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第 X

个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场 i 到达农场 X 的距离是

20，那么总路程就是

。帮助 Bessie 找出最方便的地点来举行大集会。

∮ 3. 数位DP

不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，在 a 和 b 之间，包括 a 和 b ，总共有多

少个 windy 数？

 

s

ca

nf

("

%

d

",

&

n

);

 

for

(

i

=

1

;

i





n

;

i





)

s

ca

nf

("

%

d

",

&

f

[

i

][

1

]);

 

for

(

i

=

1

;

i

<

n

;

i





)

s

ca

nf

("

%

d

%

d

",

&

a

,

&

b

),

p

a

n

[

a

]





,

a

dd

(

b

,

a

);

 

for

(

i

=

1

;

i





n

;

i





)

   

if

(!

p

a

n

[

i

]){

     

dfs

(

i

);

     

printf

("

%

d

\

n

",

m

a

x

(

f

[

i

][

0

],

f

[

i

][

1

]));

     

return

0

;

   }

}

18

19

20

21

22

23

24

25

26

27

#

in

c

lude

<

a

lgorithm

>

#

in

c

lude

<

c

string

>

#

in

c

lude

<

c

stdio

>

#

define

LL

long

#

define

R

e

register

int

using

n

a

mesp

ac

e

std

;

c

onst

LL

N

=

1

e

5

+

3

,

inf

=

1

e

18

;

int

n

,

m

,

x

,

y

,

z

,

o

,

A

[

N

],

S

[

N

],

dis

[

N

],

size

[

N

],

he

a

d

[

N

];

LL

a

ns

=

inf

,

f

[

N

],

g

[

N

];

stru

c

t

QAQ

{

int

w

,

to

,

a

[

N





1

];

inline

void

a

dd

(

R

e

x

,

R

e

y

,

R

e

z

){

a

[





o

].

w

=

z

,

a

[

o

].

to

=

y

,

a

[

o

].

he

a

d

[

x

],

he

a

d

[

x

]

=

o

;}

inline

void

in

(

R

e

&

x

){

 

int

f

=

0

;

x

=

0

;

c

h

a

r

c

=

get

c

h

a

r

();

 

while

(

c

<

'

0

'





c

>

'

9

')

f

|

=

c





'-',

c

=

get

c

h

a

r

();

 

while

(

c





'

0

'





c





'

9

')

x

=

(

x





1

)

+

(

x





3

)

+

(

c

^

48

),

c

=

get

c

h

a

r

();

 

x

=

f

?-

x

:

x

;

}

inline

void

dfs

1

(

R

e

x

,

R

e

f

a

){

 

size

[

x

]

=

1

,

S

[

x

]

=

A

[

x

];

 

for

(

R

e

i

=

he

a

d

[

x

],

to

;

i

;

i

=

a

[

i

].

if

((

to

=

a

[

i

].

to

)



f

a

)

   

dis

[

to

]

=

a

[

i

].

w

,

dfs

1

(

to

,

x

),

S

[

x

]

+=

S

[

to

],

size

[

x

]

+=

size

[

to

],

f

[

x

]

+=

f

[

to

]

+

(

LL

)

S

[

to

]*

a

[

i

].

w

;

}

inline

void

dfs

2

(

R

e

x

,

R

e

f

a

){

 

if

(

f

a

)

g

[

x

]

=

g

[

f

a

]

+

f

[

f

a

]-

f

[

x

]-(

LL

)

S

[

x

]*

dis

[

x

]

+

(

LL

)(

S

[

1

]-

S

[

x

])*

dis

[

x

];

 

for

(

R

e

i

=

he

a

d

[

x

],

to

;

i

;

i

=

a

[

i

].

if

((

to

=

a

[

i

].

to

)



f

a

)

dfs

2

(

to

,

x

);

 

a

ns

=

min

(

a

ns

,

f

[

x

]

+

g

[

x

]);

}

int

m

a

in

(){







freopen

("

123

.

txt

","

r

",

stdin

);

 

in

(

n

),

m

=

n

-

1

;

 

for

(

R

e

i

=

1

;

i





n

;





i

)

in

(

A

[

i

]);

 

while

(

m





)

in

(

x

),

in

(

y

),

in

(

z

),

a

dd

(

x

,

y

,

z

),

a

dd

(

y

,

x

,

z

);

 

dfs

1

(

1

,

0

),

dfs

2

(

1

,

0

),

printf

("

%

lld

\

n

",

a

ns

);

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

20

繁凡的 ACM 模板

————————————————————————————————————————————————————————————————————————————

剩余397页未读，继续阅读

繁凡的ACM编程竞赛模板集合

ACM模板1

最好最全的ACM模板

ACM模板ACM 模板

acm模板_acm模板

上海交大ACM模板_上海交大ACM模板_ACM模板_

ACM模板-f_zyj.zip_ACM模板_ACM模板-f_zyj_CSDN积分_acm必备模板_f_zyj ACM

ACM模板大全（各个高校的ACM模板）

kuangbin的ACM模板（新）_ACM模板_ACM算法总结_

ACM模板(浙大)_算法竞赛_ACM模板_ACM_源码

中山大学ACM模板.zip_中山大学ACM模板

最新资源