题解 P1164 【小A点菜】

### 代码和楼上楼下的都差不了太多，我就来解释一下如何推出来下面的这个式子的吧 ## f[j]+=f[j-a[i]] # 过程1 ## f[i][j]表示前i个菜品恰好花费j元的方案数 然后我们来考虑如何转移： 首先，因为f数组存储的是方案数，所以思路可以是它可以由那些方案转移过来 1.第一种可行的方案是买当前第i道菜品，这个时候前i-1个物品所需要的钱应该是j-a[i],** 也就是说前i个物品中所有能凑出j-a[i]元的方案再加上当前这道菜品，就可以变成前i个物品所需的钱为j的方案数。**即f[i][j]+=f[i-1][j-a[i]] 2.不买当前第i道菜品，这时候，也就是前i-1个物品凑成j的方案，即f[i][j]+=f[i-1][j]; **注意这里是方案的叠加，因为每一种方案都是可行的。** 你可能以为现在已经结束了，但实际上你还没有考虑一种方案，当前第i种物品恰好为j元钱，所以可以只买它自己。这种情况其实包含在1中，但是由于f[i][0]=0，所以不会算入这种情况。所以我们要把所有的f[i][0]更新成1，这样就可以计算上面所述的那种情况。 然后你就可以得到一份这样的代码 ```cpp #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define N 110 using namespace std; int n,m,a[N],f[N][10010]; int main() { //freopen(".in","r",stdin); //freopen(".out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=0;i<=n;i++) //注意这里要从0开始 f[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f[i][j]+=f[i-1][j]; if(j>=a[i]) f[i][j]+=f[i-1][j-a[i]]; } cout<<f[n][m]; return 0; } ``` # 过程2 ## 接下来就是如何把数组从2维降到1维了 我们先来考虑这样的一个问题，我们要输出a*b的答案，如果硬要用数组做的话可以用一个for循坏从1到a然后另s[i]=s[i-1]+b;最后输出s[a]。 但是通常情况下，我们都是直接用s+=b来实现这个问题，这就是一种数组降维。为什么可以降下来，因为这个问题我们每一次只会使用到i-1，而i-1就是上一次做完留下来的值，所以根本不需要用数组来做这个问题。 然后回到原问题，我们发现f数组的第一维每次也只是使用到了i-1，所以说我们可以给f数组降维。 但是这个时候需要注意一个问题，我们的第二层for循环不能正着跑了，为什么？我们可以观察一下下面两幅图片   第一个图片表示倒着跑，这个时候遍历到的当前的j就是上一次的j 而第二个图片，遍历到的j是刚刚更新了一次的j 最终代码 ```cpp #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define N 110 using namespace std; int n,m,a[N],f[10010]; int main() { //freopen(".in","r",stdin); //freopen(".out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); f[0]=1; for(int i=1;i<=n;i++) for(int j=m;j>=a[i];j--) f[j]=f[j]+f[j-a[i]]; cout<<f[m]; return 0; } ``` ------------ 我的蒟蒻思维，没有跳跃，供蒟蒻使用