POJ 1742 Coins
题目
◇题目传送门◆
题目大意
有NN种面值为 的硬币，每种硬币有cici个，求能凑成多少个11到 之间的面值。
思路
非常标准的多重背包。
我们定义f[i][j]f[i][j]为使用前ii种硬币能否凑成 。
可得状态转移方程：
其中，循环条件为1≤i≤N,1≤j≤M,0≤k≤c[i]1≤i≤N,1≤j≤M,0≤k≤c[i]，边界为f[0][0]=1f[0][0]=1。答案就是在f[N][i](1≤i≤M)f[N][i](1≤i≤M)中，值为真的个数。
不难发现，这个DP的时间复杂度为O(M∑Ni=1ci)O(M∑i=1Nci)。根据题目数据范围，这个DP是要T的。
我们尝试改变一下状态定义。
定义f[i][j]f[i][j]为用前ii中硬币凑成 后，第ii种硬币剩余的个数。若值为 则表示jj无法由前 种硬币凑成。
接着来讨论一下状态转移方程：
情况一：前i?1i?1种硬币已经凑成jj
对于这种情况，我们不难发现，
。
情况二：要凑的jj比当前硬币面值小
我们也可以发现，这时的
。
情况三：前ii种硬币刚好凑成或无法凑成
不难发现，这时的f[i][j]=?1f[i][j]=?1。
情况四：其他情况
我们可以发现，该情况可递归为f[i][j?v[i]]f[i][j?v[i]]，即取走一个硬币，使得当前的jj减少
。
所以，该状态的转移为f[i][j]=f[i][j?v[i]]?1f[i][j]=f[i][j?v[i]]?1。
综上，我们得出状态转移方程：
其中1≤i≤N,0≤j≤M1≤i≤N,0≤j≤M。
时间复杂度就降至O(NM)O(NM)，可以过时间限制。
最后，我们再使用滚动数组，即可得到正解。
正解代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=100;
const int Maxm=100000;
int N,M,f[Maxm+5];
int a[Maxn+5],c[Maxn+5];
int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifwhile(scanf("%d %d",&N,&M)!=EOF&&N&&M) {for(int i=1;i<=N;i++)scanf("%d",&a[i]);for(int i=1;i<=N;i++)scanf("%d",&c[i]);memset(f,-1,sizeof f);f[0]=0;for(int i=1;i<=N;i++) {for(int j=0;j<=M;j++) {if(f[j]>=0)f[j]=c[i];else if(j<a[i]||f[j-a[i]]<=0)f[j]=-1;else f[j]=f[j-a[i]]-1;}}int ans=0;for(int i=1;i<=M;i++)if(f[i]>=0)ans++;printf("%d\n",ans);}return 0;
}