（DP+组合数）[Lydsy2017省队十连测]商店购物

本文主要是介绍（DP+组合数）[Lydsy2017省队十连测]商店购物，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[Lydsy2017省队十连测]商店购物

Description
在 Byteland一共开着 n家商店，编号依次为 1到 n，其中编号为1到 m的商店有日消费量上限，第 i家商店的日消费量上限为wi。Byteasar每次购物的过程是这样的：依次经过每家商店，然后购买非负整数价格的商品，并在结账的时候在账本上写上在这家商店消费了多少钱。当然，他在这家商店也可以什么都不买，然后在账本上写上一个0。这一天， Byteasar日常完成了一次购物，但是他不慎遗失了他的账本。他只记得自己这一天一共消费了多少钱，请写一个程序，帮助 Byteasar计算有多少种可能的账单。

• Input
  第一行包含三个正整数
  n, m, k，分别表示商店的个数、有限制的商店个数以及总消费量。
  第二行包含 m个整数，依次表示 w1;w2…wm。
  1 ≤ m ≤ n，0≤ wi ≤ 300，1 ≤ n, k ≤ 5000000
  m<=300

• Output
  输出一行一个整数，即可能的账单数，由于答案可能很大，请对1000000007取模输出。

Sample Input

3 2 8
2 1

Sample Output

6

HINT
6 种方案分别为：

{0; 0; 8};
{1; 0; 7}; 
{2; 0; 6};
{0; 1; 7};
{1; 1; 6};
{2; 1; 5}。

我首先看到这道题：DP！！
对，没错这显然是DP可写的。所以我们考虑DP的写法。

20分代码

首先我们先做简单的背包：
$f_{i,j}$为前个商店总消费为j的方案数，易得方程：
$$f_{i,j}=\sum _{k=j-w_i}^j{f}_{i-1,k},i<=m$$

$$f_{i,j}=\sum _{k=0}^j{f}_{i-1,k},m<i<=n$$
所以用 O(nk^2) 枚举一下就可以了。

50分代码

我们发现状态的转移的是$f_{i-1}$上的一段连续区间，那么我们只用搞一个前缀和。
设$s_{i,j}$
$$s_{i,j}=\sum _{k=0}^j{f}_{i,k}$$

即

$$s_{i,j}=s_{i,j-1}+f_{i,j}$$
每次求出第i天的$f_{i,j}$数组值就再枚举求出$s_{i,j}$即可。
我们也可以得到DP式：
$$f_{i,j}=s_{i-1,j}-s_{i-1,j-w_i-1},i<=m$$

$$f_{i,j}=s_{i-1,j},m<i<=n$$
当然我们也可以动态地维护前缀和。
对于$1-m$，如下（使用了滚动数组）。复杂度 O(nk)
$sum$为前缀和。

last=now;
now^=1;
j=0;
sum=0;
while(j<=tot)
{sum+=f[last][j];sum%=1000000007;if(j>w[i]){sum-=f[last][j-w[i]-1];sum%=1000000007;sum+=1000000007;sum%=1000000007;}sum+=1000000007;sum%=1000000007;f[now][j]=sum;++j;
}

100分代码

由于$m$很小，容易想到先预处理出前m家商店，再用组合数求出之后的值。
设$tot$为前m家商店的$w_i$总合。
不难看出
$$ans=\sum _{j=0}^{min(k,tot)}{f}_{m,j}\ast \left(\genfrac{}{}{0ex}{}{k-j+n-1}{k-j}\right)$$
其中组合数可以由逆元求出。复杂度 O(mk+k+n)
AC代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<iostream>
using namespace std;
long long n,m;
long long k,w[310],f[2][100600],sum=0,tot=0;
long long cc[10000100],dd[10000100],ans=0;
inline long long mul(long long x,long long y)
{long long res=1;while(y){	if(y&1) res=(res*1ll)%1000000007*(1ll*x)%1000000007;y>>=1;x=((x*1ll)*(1ll*x))%1000000007;}return res;
}
inline long long getc(long long x,long long y)
{if(x<y) return 0;return ((cc[x]*1ll*(dd[y]*1ll)%1000000007)*(1ll*dd[x-y]))%1000000007;
}
int main()
{scanf("%lld%lld%lld",&n,&m,&k);int i=1,j=1;while(i<=m){scanf("%lld",&w[i]);++i;}cc[0]=1;i=1;while(i<=10000000){cc[i]=((cc[i-1]*1ll)%1000000007*(1ll*i))%1000000007;++i;}dd[10000000]=mul(cc[10000000],1000000005);i=10000000;while(i){dd[i-1]=((dd[i]*1ll)%1000000007*(1ll*i))%1000000007;--i;}n-=m;f[0][0]=1;i=1;int last,now=0;while(i<=m){tot+=w[i];last=now;now^=1;j=0;sum=0;while(j<=tot){sum+=f[last][j];sum%=1000000007;if(j>w[i]){sum-=f[last][j-w[i]-1];sum%=1000000007;sum+=1000000007;sum%=1000000007;}sum+=1000000007;sum%=1000000007;f[now][j]=sum;++j;}++i;}if(!n){if(k<=tot) ans=f[now][k];else ans=0;}else{i=min(k,tot);while(i>=0){ans+=(f[now][i]*(1ll*getc(k-i+n-1,k-i))%1000000007)%1000000007;--i;}}ans%=1000000007;printf("%lld\n",ans);return 0;
}

总结

是一道很好的题目，给足了暴力分，数据也引导人循序渐进。
有难度但想到正解并不难。是一道水题。

这篇关于（DP+组合数）[Lydsy2017省队十连测]商店购物的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---