poj 3181 动态规划

川长思鸟来 2022-08-03 08:23 149阅读 0赞

Dollar Dayz

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 4840</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 1842</td> 
  </tr> 
 </tbody> 
</table>

Description

Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are:

1 @ US$3 + 1 @ US$2
    
            1 @ US$3 + 2 @ US$1
    
            1 @ US$2 + 3 @ US$1
    
            2 @ US$2 + 1 @ US$1
    
            5 @ US$1

Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).

Input

A single line with two space-separated integers: N and K.

Output

A single line with a single integer that is the number of unique ways FJ can spend his money.

Sample Input

5 3

Sample Output

Source

[USACO 2006 January Silver][]

给定n和k，k代表有k个商品价格分别是1-k，每个商品的数量无限，n代表有n元钱，求把这n元钱花完总共有多少种方法。

开始发现这题跟以前做的题很像，很快就写出了推导式，但是初始化的时候却出现了问题。最开始的时候将从1-k的dp全部设置为1，最后发现重复计算了很多。

后来网上搜了一下才明白要把dp【0】设置为1.这样就不会重复计算。

中间运算会超过long long的表示范围，因此用数组模拟就行。

dp\[i\]\[0..50\]表示第i个数有多少种组合方式。dp数组第二维表示组合方式的数量。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int dp[1111][55];
    int v[111];
    
    void add(int n,int m)
    {
        int tmp=0;
        for(int i=0;i<50;i++)
        {
           dp[n][i]+=dp[m][i]+tmp;
           if(dp[n][i]>=10)
           {
               tmp=1;
               dp[n][i]%=10;
           }
           else tmp=0;
        }
    
    }
    
    int main()
    {
        int n,k;
        while(~scanf("%d%d",&n,&k))
        {
            mem(dp,0);
            dp[0][0]=1;
            for(int i=1;i<=k;i++) //从每一个商品开始看它能组成哪些钱数
            {
                for(int j=i;j<=n;j++)
                {
                    add(j,j-i);
                }
            }
           int i=50;
           while(i>0 && dp[n][i]==0)--i;
           while(i>=0)
           {
               printf("%d",dp[n][i]);
               --i;
           }
           puts("");
        }
        return 0;
    }

[USACO 2006 January Silver]: http://poj.org/searchproblem?field=source&key=USACO+2006+January+Silver