poj1742 coins dp

题目链接：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\n",ans);
	  scanf("%d%d",&n,&m);
    }
    //fclose(stdin);
	return 0;
}

（顺便贴一组n=100，m=100000的测试数据，答案是86085，如果有WA的可以对着这组数据测一下

100 100000
2753 23850 78826 76015 82258 2875 9510 62449 37906 75392 7823 19447 17253
12571 57217 66434 97242 47551 40323 72899 14697 1399 81251 57900 25190 45590
94071 68477 10082 67472 56318 18265 64794 85219 77138 95537 27968 86715 56437
18417 6205 6682 77321 11135 25641 74087 53250 49579 95416 49504 72545 17202
2805 73705 75722 77388 11810 84569 40207 98880 572 51537 77363 23819 25157
73699 8744 89659 22913 89405 42796 66867 85384 28612 25656 53238 14200 82294
66734 36245 81715 70882 12802 49524 17568 22292 55323 74886 31722 52457 41995
82688 20611 11955 32356 30652 25390 82318 91741 12958 68 88 81 41 55 20 40 51
78 48 16 70 3 32 3 41 72 81 56 74 62 99 67 89 34 43 77 59 58 23 28 78 100 15 5
17 48 51 38 73 59 66 82 49 59 56 51 6 85 71 19 74 71 16 74 11 33 16 77 70 55
39 58 55 10 94 25 94 4 10 99 6 26 4 59 71 51 26 100 67 21 28 47 63 7 57 90 91
26 24 91 58 67 10 3 6 55 65 41 55 0 0

poj1742 coins dp

原文：https://www.cnblogs.com/edmunds/p/12442642.html