Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are:

        1 @ US$3 + 1 @ US$2


        1 @ US$3 + 2 @ US$1


        1 @ US$2 + 3 @ US$1


        2 @ US$2 + 1 @ US$1


        5 @ US$1

Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).

A single line with two space-separated integers: N and K.

A single line with a single integer that is the number of unique ways FJ can spend his money.

5 3

5

完全背包+高精度数

没有优化直接wa，是数值范围太小

#include<iostream>

using namespace std;

int dp[][];

int main(){

    int n,k;

    cin>>n>>k;

    dp[][]=;

    for(int i=;i<=k;i++){

        for(int j=;j<=n;j++){

            for(int k=;k*i<=j;k++){

                dp[i][j]+=dp[i-][j-k*i];

            }

        }

    }

    cout<<dp[k][n];

    return ;

} 

100000000000000000。

#include<iostream>

using namespace std;

unsigned long long dp[][][];

#define LIMIT_ULL 100000000000000000

int main(){

    int n,k;

    cin>>n>>k;

    dp[][][]=;//低位

    for(int i=;i<=k;i++){

        for(int j=;j<=n;j++){

            for(int k=;k*i<=j;k++){

                dp[i][j][]+=dp[i-][j-k*i][];

                dp[i][j][]+=dp[i-][j-k*i][];

                dp[i][j][]+=dp[i][j][]/LIMIT_ULL;//低位的进位加到高位

                dp[i][j][]=dp[i][j][]%LIMIT_ULL;//低位去除进位

            }

        }

    }

    if(dp[k][n][]){

        cout<<dp[k][n][];

    }

    cout<<dp[k][n][];

    return ;

} 

#include<iostream>

using namespace std;

unsigned long long dp[][][];

#define LIMIT_ULL 100000000000000000

int main(){

    int n,k;

    cin>>n>>k;

    dp[][][]=;

    for(int i=;i<=k;i++){

        for(int j=;j<=n;j++){

            if(j<i){

                dp[i][j][]=dp[i-][j][];

                dp[i][j][]=dp[i-][j][];

            }

            else{

                dp[i][j][]=dp[i-][j][]+dp[i][j-i][];

                dp[i][j][]=dp[i-][j][]+dp[i][j-i][];

                dp[i][j][]+=dp[i][j][]/LIMIT_ULL;

                dp[i][j][]=dp[i][j][]%LIMIT_ULL;

            }

        }

    }

    if(dp[k][n][]){

        cout<<dp[k][n][];

    }

    cout<<dp[k][n][];

    return ;

}