【算法】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
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int maxn=10010,maxV=30;int n,m,a[maxV];ll f[maxn][maxV];int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)scanf("%d",&a[i]);    f[0][0]=1;    for(int i=1;i<=m;i++){        for(int j=1;j<=n;j++)if(i-a[j]>=0){            for(int k=0;k<=j;k++)f[i][j]+=f[i-a[j]][k];        }    }    ll ans=0;    for(int i=0;i<=n;i++)ans+=f[m][i];    printf("%lld",ans);    return 0;}
        
       
      

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

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

每个面值视为物品体积，求总体积为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]];