UVA674 Coin Change 简单的DP - c++编程基础

刚开始一直都是RE，这道题目题目的意思跟目的跟HDU2069是一样的，只是题目要求有了点变化，HDU2069是最多用100个钱币，这里呢最多输入的钱为7489，自然而然最多用到的钱币为7489个，所以一开始用了一样的方法，把数组开为8000*8000，可是一直RE，不知道为什么，也没有超内存，而且范围最多也不会超8000的，现在还不清楚，于是只能换思路了，仔细看看这道题目完全可以看作一个一维背包来做，意思就是给你一个容量为n的背包，让你用体积有1，5，10，25，50五种不同的东西来填装，状态转移方程就很好推了

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // ll dp[8000+5]; int value[6]={0,1,5,10,25,50}; void init() { memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=1;i<=5;i++) for(int j=value[i];j<=7489;j++) dp[j] += dp[j-value[i]]; } int main() { int n; init(); while(cin>>n) { cout<