poj3181 Dollar Dayz

发布时间：2020-12-14 02:30:03 所属栏目：大数据来源：网络整理

导读：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 too

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

题意：给你两个数n，k，让你用1到k这k个数表示n，问有几种方法，本质是整数的拆分。因为最后结果比较大，超过long long,所以用两个long long连接起来，设两个数组a[][],b[][]分别表示没有超过long long的部分以及超过long long 部分。

其中a[n][m]表示n用一些数拆分，其中最大的数不超过m的方案数，画图可以看到，当n<m时，a[i][j]=a[i][i];当n>=m时，a[i][j]=(a[i][j-1]+a[i-j][j])%inf;初始化的时候要令a[0][i]=1,因为a[2][2]=a[0][2]+a[2][1];

6
5 + 1
4 + 2,4 + 1 + 1
3 + 3,3 + 2 + 1,3 + 1 + 1 + 1
2 + 2 + 2,2 + 2 + 1 + 1,2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

#include<stdio.h>
#include<string.h>
#define ll long long
ll a[1006][106],b[1006][106];
ll inf;
int main()
{
int n,m,i,j;
inf=1;
for(i=1;i<=18;i++){
inf*=10;
}
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(a,sizeof(a));
memset(b,sizeof(b));
for(i=1;i<=m;i++){
a[0][i]=1;
}
for(i=1;i<=n;i++){
a[i][1]=1;
}
for(j=1;j<=m;j++){
a[1][j]=1;
}

for(j=2;j<=m;j++){
for(i=2;i<=n;i++){
if(i<j){
a[i][j]=a[i][i];
b[i][j]=b[i][i];
}
else{
a[i][j]=(a[i][j-1]+a[i-j][j])%inf;
b[i][j]=b[i][j-1]+b[i-j][j]+(a[i][j-1]+a[i-j][j])/inf;
}
//printf("%d %d %dn",j,a[i][j]);
}
}
if(b[n][m])
printf("%lld",b[n][m]);
printf("%lldn",a[n][m]);
}
return 0;
}

这题也可以用完全背包，并用高精度模拟，状态转移方程：dp[j]+=dp[j-w[i]]

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
#define inf 0x7fffffff
#define ll long long
int dp[1005][60];
void add(int a,int b){
    int i,j;
    for(i=1;i<=50;i++){
        if(dp[a][i]+dp[b][i]<=9){
            dp[a][i]=dp[a][i]+dp[b][i];
        }
        else{
            dp[a][i]=(dp[a][i]+dp[b][i])%10;
            dp[a][i+1]++;
        }
    }
}

int main()
{
    int n,k,t;
    while(scanf("%d%d",&m,&k)!=EOF)
    {
        memset(dp,sizeof(dp));
        dp[0][1]=1;
        for(i=1;i<=k;i++){
            for(j=i;j<=m;j++){
                add(j,j-i);
            }
        }
        t=50;
        while(t>=2 && dp[m][t]==0)t--;

        for(i=t;i>=1;i--){
            printf("%d",dp[m][i]);
        }
        printf("n");
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!