C++(g++ 7.5.0) 解法, 执行用时: 7ms, 内存消耗: 840K, 提交时间: 2022-09-16 15:41:28

#include<iostream>
using namespace std;
int dp[100010];
int t,n;
int b[]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};
const int N =1e9+7;

void solve(){
	dp[0]=1;
	for(int i=0;i<13;i++){
		for(int j=b[i];j<=100000;j++){
			dp[j]+=dp[j-b[i]];
			dp[j]=dp[j]%N;
		}
	}
}
int main()
{	


	solve();
	cin>>t;
	while(t--){
		cin>>n;
		cout<< dp[n]<<endl;
	} 
	return 0;
 } 

C++14(g++5.4) 解法, 执行用时: 47ms, 内存消耗: 992K, 提交时间: 2019-06-06 21:51:48

#include<iostream>
#define MOD 1000000007
#define MAX 100010
using namespace std;
int main(){
	int n,t,ar[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};
	cin>>t;
	while(t--){
		int dp[MAX]={1};
		cin>>n;
		for(int i=0;i<13;i++)
			for(int j=ar[i];j<=n;j++)
				dp[j]=(dp[j]+dp[j-ar[i]])%MOD;
		cout<<dp[n]<<endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 888K, 提交时间: 2020-02-17 16:18:36

#include<iostream>
#define MOD 1000000007
#define MAX 100010
using namespace std;
int main()
{
	int n,t,ar[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};
	cin>>t;
	while(t--)
	{
		int dp[MAX]={1};
		cin>>n;
		for(int i=0;i<13;i++)
		for(int j=ar[i];j<=n;j++)
		dp[j]=(dp[j]+dp[j-ar[i]])%MOD;
		cout<<dp[n]<<endl;
	}
	return 0;
}

Python3 解法, 执行用时: 426ms, 内存消耗: 9320K, 提交时间: 2022-08-02 21:55:47

res = [1, 2, 5, 10, 20 ,50, 100, 200, 500, 1000, 2000, 5000, 10000]
dp = [0] * 100001
dp[0] = 1
mod = 10 ** 9 + 7
for i in res:
    for j in range(i, 100001):
        dp[j] = (dp[j] + dp[j - i]) % mod

n = int(input())
for _ in range(n):
    print(dp[int(input())])