動态規劃（6）——VF（NYOJ269）*

英文題目，比較難懂。大概意思：就是求1到10^9裡的數滿足每位相加之和等于s的數的個數。

比如1到10^9中的數滿足每位相加起來都是1的有10個：1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000；

AC代碼如下：

       看别人的，還不是太懂，先記下來，慢慢琢磨吧。

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

34

35

36

37

38

39

40

41

42

43

<code>#include&lt;iostream&gt;</code>

<code>#include&lt;stdio.h&gt;</code>

<code>#include&lt;stdlib.h&gt;</code>

<code>#include&lt;string.h&gt;</code>

<code>using</code>

<code>namespace</code> <code>std;</code>

<code>int</code> <code>dp[10][82];</code>

<code>int</code> <code>main()</code>

<code>{</code>

<code>    </code><code>int</code>

<code>n;</code>

<code>    </code><code>memset</code><code>(dp,0,</code><code>sizeof</code><code>(dp));</code>

<code>    </code><code>for</code><code>(</code><code>int</code>

<code>i=1;i&lt;10;i++)</code>

<code>    </code><code>{</code>

<code>        </code><code>dp[1][i]=1;</code><code>//1位數中每位相加為1……10的都是1個。</code>

<code>    </code><code>}</code>

<code>i=1;i&lt;10;i++)</code><code>//數的位數，從位數為1到位數為9</code>

<code>        </code><code>for</code><code>(</code><code>int</code>

<code>j=1;j&lt;=i*9;j++)</code><code>//某個數的各個位數相加之和為j,最大為9*9=81</code>

<code>        </code><code>{</code>

<code>            </code><code>for</code><code>(</code><code>int</code>

<code>k=0;k&lt;=9&amp;&amp;k&lt;=j;k++)</code><code>//?</code>

<code>            </code><code>{</code>

<code>                </code><code>dp[i][j]+=dp[i-1][j-k];</code><code>//?</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>    </code><code>while</code><code>(</code><code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;n)!=EOF)</code>

<code>        </code><code>int</code>

<code>ans=0;</code>

<code>        </code><code>if</code><code>(n==1)</code><code>//如和就是1,則就輸出10就ok</code>

<code>            </code><code>printf</code><code>(</code><code>"%d\n"</code><code>,10);</code>

<code>            </code><code>continue</code><code>;</code>

<code>        </code><code>else</code>

<code>i=1;i&lt;10;i++)</code><code>//不然将和為n的1到9位數的個數全都加起來</code>

<code>                </code><code>ans+=dp[i][n];</code>

<code>            </code><code>printf</code><code>(</code><code>"%d\n"</code><code>,ans);</code>

<code>    </code><code>return</code>

<code>0;</code>

<code>}</code>

　　

<dl></dl>

<dd></dd>