C語言動態規劃

 

Problem Description Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:

1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000). Input A single line with a single integer, N. Output The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation). Sample Input

7

Sample Output

6

 

題目大意：

輸入一個整數,將這個數分解成不定個正數只和，要求這些數必須是2的k次方(k為大於等於0的正數).輸出分的方法種數.(由於當輸出整數過大時,種數很大只輸出最後9位)

 

思路一：

 

設a[n]為和為 n 的種類數；
根據題目可知，加數為2的N次方，即 n 為奇數時等於它前一個數 n-1 的種類數 a[n-1] ，若 n 為偶數時分加數中有無 1 討論，即關鍵是對 n 為偶數時進行討論：
1.n為奇數，a[n]=a[n-1]
2.n為偶數：
（1）如果加數裡含1，則一定至少有兩個1，即對n-2的每一個加數式後面 +1+1，總類數為a[n-2]；
（2）如果加數裡沒有1，即對n/2的每一個加數式乘以2，總類數為a[n/2]；
所以總的種類數為：a[n]=a[n-2]+a[n/2];

代碼：

 

#include
__int64 a[1000001];
int main()
{
    __int64 n;
 int i;
    a[1]=1;a[2]=2;
    for(i=3;i<1000001;i++)
    {
        if(i%2==0)
            a[i]=a[i-2]+a[i/2];
        else
            a[i]=a[i-1]; 
        a[i]%=1000000000;   //控制最多為9位.
    }
    while(scanf("%I64d",&n)!=EOF)
        printf("%I64d\n",a[n]);
    return 0;
}

 

思路二：

DP思想,

假如只能用1構成那麼每個數的分的方法種數就是1.

如果這個時候能用 2 構成，那麼對於大於等於 2 的數 n 就可以由 n - 2 和 2 構成 就轉化為 求 n - 2 的種數那麼就是 d [ n ] = d [ n-2 ] + d [ n ] (前面 d [ n-2 ] 表示數n可以由2構成的種數,後面加的 d [ n ] 表示數n只能由 1 構成的種數.)

那麼狀態轉移方程式子就出來了(c [ n ] = 2^n)

d [ n ] [ k ] = d [ n ] [ k - 1 ] + d [ n - c [ k ] ] [ k ] ;

循環降維：

d [ n ] = d [ n ] + d [ n - c [ k ] ] ;

 

代碼：

 

#include  
#include 
__int64 d[1000005],c[25],n,i,j;  
int main()  
{  
    while(scanf("%d",&n)!=EOF) 
    {
        memset(d,0,sizeof(d));
        c[0]=d[0]=1;  
    for(i=1;i<=24;i++)  
        c[i]=c[i-1]<<1;  
    for(i=0;i<=24&&c[i]<=n;i++)  
        for(j=c[i];j<=n;j++)  
            d[j]=(d[j]+d[j-c[i]])%1000000000;  
        printf("%d\n",d[n]);
    }
            return 0;
}