程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> C語言動態規劃

C語言動態規劃

編輯:關於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;
}  


 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved