当前位置:编程学习 > C/C++ >>

uva - 11137 - Ingenuous Cubrency

题意:用21种球币:1^3, 2^3, ..., 21^3(数量不限)来组成数n来几种方法。

——>>汝佳神牛白书动态规划中通过率最高的一题,却让我搞了大半夜也没弄出来,今早一试却AC!

dp(i, j)表示用前i种球币组成j元钱的方法数;

状态转移方程:dp(i, j) = dp(i-1, j) + dp(i, j-v[i]);(对于第i种球币,要么不用(dp(i-1, j))),要么用(dp(i, j - v[i]))

之前一起数字一到9282就开始不对,因为是一次输出:cout<<dp(21, i)<<endl;

后将前9999种钱数都先存入数组,便解决了这数大不对的问题,具体原因……(求解答)

[cpp] 
#include <iostream> 
#include <string.h> 
 
using namespace std; 
 
const int maxn = 10000 + 10;        //最大数不超过10000 
 
int v[30];      //用来存21种球币  www.zzzyk.com
 
long long d[30][maxn];      //d[i][j]用来存用前i种球币组成j元钱的方法数 
 
long long dp(int i, int j)      //动态规划:前i种球币组成j元钱的方法数 

    if(d[i][j] > 0) return d[i][j];     //如果已经记录过了,直接返回 
    if(j < 0)   return 0;       //如果在dp(i, j-v[i])出现了j-v[i]<0的情况,返回0,不可能用正数的和来表示一个负数 
    if(i == 1 || j == 0)        //dp(i-1, j)必然出现i == 1的情况,用面值为1的球币表示任一正数,只有1种方法,可能出现j-v[i] == 0,说明那种面值的球币恰能一次表示,也记1种方法 
    { 
        d[i][j] = 1; 
        return 1; 
    } 
 
    d[i][j] = dp(i-1, j) + dp(i, j-v[i]);       //状态转移,前于第i种球币,要么不用,要么用 
 
    return d[i][j]; 

 
int main() 

    int i; 
    for(i = 1; i <= 21; i++)        //设置21种球币 
        v[i] = i * i * i; 
 
    memset(d, 0, sizeof(d));        //置-1,用来标记有没被修改过 
 
    for(i = 1; i < 10000; i++)      //先将前9999元的情况存入数组 
        dp(21, i); 
 
    while(cin>>i) 
    { 
        cout<<d[21][i]<<endl;       //直接从数组中读出 
    } 
 
    return 0; 

 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,