绵阳低价网站建设,免费素材网站设计,购物网站个人中心模板,征婚网站开发题意#xff1a;问在现有面值金额下 输入一个m可以由多少种不同的金额组成
那么可以定义dp[i]表示i金额由多少种不同的金额组成方式
转移方程#xff1a;dp[i] (dp[i] dp[i-cost[j])%mod#xff1b; 首先要定义dp[0] 1#xff1b; 然后枚举面值 看不同数目下该面值可…题意问在现有面值金额下 输入一个m可以由多少种不同的金额组成
那么可以定义dp[i]表示i金额由多少种不同的金额组成方式
转移方程dp[i] (dp[i] dp[i-cost[j])%mod 首先要定义dp[0] 1 然后枚举面值 看不同数目下该面值可以组成那些金额 然后通过状态转移累计不同的组成方式
#includebits/stdc.h
using namespace std;
int a[13] {1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};
const int mod 1e97;
int dp[100010];
int main()
{int m;scanf(%d,m);dp[0]1;for(int i0;i13;i){for(int ja[i];jm;j){if(dp[j-a[i]])dp[j] (dp[j]dp[j-a[i]])%mod; }}printf(%d\n,dp[m]);return 0;
}
