poj 3181

本文主要是介绍poj 3181，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你n元钱和无限个价钱为1~k的物品，让你求有多少种方法花光这n元钱？

思路：

参考别人的。。

可以看成是整数的划分。

如5 3

1+1+1+1+1

1+1+1+2  1+2+2

1+1+3   2+3

设dp[i][j]为i的划分中最大数不超过j的划分总数。

则dp[i][j]=dp[i][j-1]+dp[i-j][j];

有点像组合的某个公式。

分成两个，最大数不选j的，那么为dp[i][j-1]，

最大数选中了j的，即dp[i-j][j]。

定义状态为前i个金币能组合成总金额为j的方案总数

状态转移方程为

和完全背包类似，可以化简成

在大神的博客里面学到了一招，将答案拆成两半，用两个dp数组存。一个存高18位，一个存低18位。

#include <iostream>
#include <cstring>
using namespace std;
long long  a[1010][1010],b[1010][1010],mod=1;
int main()
{int n,k;for(int i=0;i<18;++i)mod*=10;while(cin>>n>>k){memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=0;i<=k;++i)a[0][i]=1;for(int i=1;i<=n;++i)for(int j=1;j<=k;++j){if(i<j){a[i][j]=a[i][j-1];b[i][j]=b[i][j-1];}else{b[i][j]=b[i][j-1]+b[i-j][j]+(a[i][j-1]+a[i-j][j])/mod;a[i][j]=(a[i][j-1]+a[i-j][j])%mod;}}if(b[n][k])cout<<b[n][k];cout<<a[n][k]<<endl;}return 0;
}

这篇关于poj 3181的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---