天天看點

把m升水倒入n個桶中,可以有桶為空,問有多少種倒法

#include <iostream>
using namespace std;
int count;
void DPS2(int x1,int x2,int x3,int x4,int x5)
{
    if(x3>x4) return;
    for(int i=x5;i>=0;i--)
    {
        if(x1==x2&&x3+i==x4)
            count ++;
        else if(x1<x2)
            DPS2(x1+1,x2,x3+i,x4,i);
    }
}
void DPS(int x,int y)
{
    DPS2(0,y-1,0,x,x);
}
int main()
{
    count = 0;
    int m,n;
    cin >> m >> n;
    DPS(m,n);
    cout << count;
}
           

x1,x2,x3,x4,x5 分别表示目前算第x1個桶,共x2+1個桶,目前已經裝了x3升水,共需要裝x4升水,它前面的一個桶裝了x5升水。

好複雜的樣子,,隻是因為  7,3   的時候,方案有

7,0,0

6,1,0

5,2,0,

5,1,1,

4,3,0

4,2,1

3,3,1

3,2,2

共7種方法,,5,1,1, 和1,1,5 算同一個。。是以  三個數間有大小排列的關系就可以排除那個情況了

是以設定了x5 表示左邊那個桶裝了多少升水,目前桶不能裝超過x5升的水

繼續閱讀