题解 P5087 【数学】
lmrttx
2021-01-04 20:46:47
说真的，这题恶评了。
考的是01背包，这里讲下压维的做法。
定义：$dp[i]$ 表示选 $i$ 的物品的分数这和。
状态转移方程就是：
$$dp[i]=dp[i]+dp[i-1]*a[j]$$
这里的 $j$ 为区间 $[1,n]$ 中任意整数。
边界值就是 $dp[0]=1$。
状态转移方程的得来：一个状态由本身加上（分数之和）上一个状态乘取出的数（题目要求的是积），最后推得答案(就是改装了一下01背包)。
答案就是 $dp[k]$ 了。
由于**每个数只取一次**，所以使用01背包的正确性使然。
$Code$ ~~我做了点手脚，不要复制！~~
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1000000007;
ll n,k,a[100010],dp[100010];
int main(){
scanf("%ld%ld",&n,&k);
dp[0]=1;
for(register int i=1;i<=n;i++){
scanf("%ld",&a[i]);
}
for(int i=1;i<=n;i++)
for(int j=k;j>=0;j--){
dp[j]=(dp[j]+dp[j-1]*a[i])%mod;
//取模不能漏
}
printf("%ld",$dp[k]);
return 0;
}
```
谢谢阅读qwq!