【BZOJ】1708: [Usaco2007 Oct]Money奶牛的硬币

【算法】DP

【题解】

如果每个排列算一种，则令f[i]表示凑成面值为i的方案数，容易推出f[i]+=f[i-a[j]]。

现在是每个组合才算一种，令f[i][j]第二维表示只使用前j种面值，f[i][j]+=f[i-a[j][k],k=0~j，这样最终算出来的方案就是按一定顺序的，不会重复计算。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=,maxV=;

int n,m,a[maxV];

ll f[maxn][maxV];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    f[][]=;

    for(int i=;i<=m;i++){

        for(int j=;j<=n;j++)if(i-a[j]>=){

            for(int k=;k<=j;k++)f[i][j]+=f[i-a[j]][k];

        }

    }

    ll ans=;

    for(int i=;i<=n;i++)ans+=f[m][i];

    printf("%lld",ans);

    return ;

}

------------------------------------------------------

以上脑洞太大了，其实是完全背包。

每个面值视为物品体积，求总体积为N的方案数。

换种思路，每次考虑加入一种面值，这样就自然不会重复算了。

f[0]=1;

for(int i=1;i<=v;i++)

　　for(int j=a[i];j<=n;j++)

　　　　f[j]+=f[j-a[i]];

巴特西

【BZOJ】1708: [Usaco2007 Oct]Money奶牛的硬币

最新文章

热门文章