poj1742 coins

题目链接：https://vjudge.net/problem/POJ-1742

有点奇特的dp。做题思路来自于挑战程序设计的多重部分和那一节。一开始过了hdu2844但是poj1742过不去，今天终于过了...

n<=100,m<=100000直接用多重背包肯定tle，所以要有一些好的状态设计。

设f[i][j]表示用到第i种面值，组成面值j，第i种还剩多少个。f[i][j]=-1表示不能组成j。那么

1. 若f[i-1][j]>=0则f[i][j]=c[i]，因为前i-1种面值可以组成j，第i种自然剩下c[i]个

2. f[i-1][j]<0

1) 若j<a[i]，f[i][j]=-1。因为前i-1种不能组成j，加上>j的a[i]肯定也不能组成j

2）若j>=a[i]   

  ① 若f[i][j-a[i]]>0，即可以组成j-a[i]还有剩余，则f[i][j]=f[i][j-a[i]]-1

  ② f[i][j-a[i]]<=0 则f[i][j]=-1。

至此就讨论完了。注意一个坑点：这题空间只有30000kb，数组只能开成一维的。还纠结过开成一维j要不要倒着循环，想了想是不对的，因为那样每个i种面值相当于只用了一次

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=100+10;
const int maxm=100000+10;
int a[maxn],c[maxn],f[maxm];
int n,m,i,j,k,ans;

int main(){
	//freopen("poj1742.txt","r",stdin);
	scanf("%d%d",&n,&m);
	while (n!=0&&m!=0){
	  for (i=1;i<=n;i++) scanf("%d",&a[i]);
	  for (i=1;i<=n;i++) scanf("%d",&c[i]);
	  memset(f,-1,sizeof(f));
	  f[0]=0;
	  for (i=1;i<=n;i++)
	    for (j=0;j<=m;j++){
	  	  if (f[j]>=0) f[j]=c[i];
	  	  else{
	  		if (j<a[i]) f[j]=-1;
	  		if (j>=a[i]){
	  			if (f[j-a[i]]>0) f[j]=f[j-a[i]]-1;
	  			else f[j]=-1;
			  }
		  }
	    }
	  ans=0;
	  for (i=1;i<=m;i++) if (f[i]>=0) ans++;
	  printf("%d
",ans);
	  scanf("%d%d",&n,&m);
    }
    //fclose(stdin);
	return 0;
}