当前位置:编程学习 > C#/ASP.NET >>

hdu 1284 钱币兑换问题 (DP)

[csharp] 
//dp(完全背包) 
#include <stdio.h> 
#include <string.h> 
#define N 35000 
int dp[N]; 
int main() 

    dp[0] = 1; 
    for(int i = 1; i <= 3; ++i) 
    {   //背包容量为N,装入质量为i 的物品 
        for(int j = i; j < N; ++j) 
        { 
            dp[j] += dp[j-i]; 
        } 
    } 
    int n; 
    while(scanf("%d", &n) != EOF) 
        printf("%d\n", dp[n]); 
    return 0; 
}<pre name="code" class="csharp">//hdu 1284 找规律  
//给出n 看能n 内有多少个 2 和多少个3  
//具体看代码和一下注视 
#include<stdio.h>  
#include <string.h>  
#define N 35000 
__int64 ans[N]; 
int main() 
{  
    int n; // 计算i 可以由多少个 2 组成  
    for(int i = 0; i < N; ++i) 
        // 后面的 +1 表示全由1组成的(只有1中情况) 
        ans[i] = i / 2 + 1;  
    //则这一行表示由 2组成的情况加上由1组成的情况  
    // 从前面往后推,看能由几个3 组成,比如 ans[3]表示钱为3时  
    // 由1,2分硬币组成的情况,可以表示成钱为0 时加上一个3分硬币(这时方法数为 
    // 钱为 0 时由1,2,3组成的情况 加上钱为3时由1,2组成的方法数) 
    // 因此 ans[i] += ans[i-3]+1;不需要后面的+1  
    for(int i = 3; i < N; ++i) ans[i] += ans[i-3]; 
    //这一行ans[i]就表示由2组成的情况加上由3组成的情况  
    // ans[6]就相当于由2组成的情况ans[6] 加上 由1,2,3组成的情况的ans[6-3]  
    // 这样往后推,就可以把 由3分组成的情况加上去  
    while(scanf("%d", &n) != EOF)  
        printf("%I64d\n", ans[n]); 
    return 0;  
}</pre><br> 
<pre></pre> 
<p></p> 
<pre></pre> 
<br> 
<p></p> 
补充:软件开发 , C# ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,