給你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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。