网上代理 建网站,重庆网上房地产信息网官网,做网站需要具备什么,表白网页链接大全正题 题目大意
n个物品#xff0c;每个物品有cic_ici元#xff0c;求有多少种方案数使得无法再买另外任何的东西。 解题思路
我们发现其实对于每种方案判断只需要考虑剩下的最小的哪一个#xff0c;所以我们可以将ccc从小到大排序。然后用fi,jf_{i,j}fi,j表示选择了1∼…正题 题目大意
n个物品每个物品有cic_ici元求有多少种方案数使得无法再买另外任何的东西。 解题思路
我们发现其实对于每种方案判断只需要考虑剩下的最小的哪一个所以我们可以将ccc从小到大排序。然后用fi,jf_{i,j}fi,j表示选择了1∼i−11\sim i-11∼i−1还没有选择时耗费了j元的方案数。 动态转移: fi,jfi1,jcifi1,jf_{i,j}f_{i1,jc_i}f_{i1,j}fi,jfi1,jcifi1,j 最后我们枚举最小没有选择的是xxx还剩余resresres元 ∑r0cx−1fn,m−r\sum_{r0}^{c_x-1}f_{n,m-r}r0∑cx−1fn,m−r code
#includecstdio
#includealgorithm
#define N 2010
#define XJQ int(1e77)
using namespace std;
int n,m,c[N],f[N][N],ans,t;
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,c[i]),ansc[i];if(ansm){printf(1);return 0;}ans0;sort(c1,c1n);//排序f[n1][0]1;//初始化for(int in;i1;i--)for(int j0;jm;j)f[i][j](f[i1][j](jc[i]?f[i1][j-c[i]]:0))%XJQ;//动态转移for(int i1;in;i){for(int j0;jc[i];j)if(m-t-j0)(ansf[i1][m-t-j])%XJQ;//计算答案tc[i];//减少剩余}printf(%d,ans);
}
