AcWing 5386. 进水出水问题(线性DP)
原题链接
困难
作者:
代码人生
,
2024-01-25 22:10:46
,
所有人可见
,
阅读 62
f[i][j]表示以i为结尾的一段,进水速度-出水速度为j的方案数
当我们面对要求两个量相等的DP问题时就可以采取这种方法
则可将f[i][j]分为四大类:①只包含i且i为进水口②只包含i且i为出水口③该段有多个水管且i为进水管④该段有多个水管且i为出水管
则状态转移方程为(代入定义可得):
①$f[i][a[i]]++$
②$f[i][-a[i]]++$
③$f[i-1][j-a[i]]$
④$f[i-1][j+a[i]]$
$最后是代码环节$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010,mod = 1e9 + 7,M = 20010,B = 10000;
int n;
int a[N],f[N][M],ans;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
for(int j=0;j<M;j++){
if(j + a[i] < M) f[i][j] = (f[i][j] + f[i - 1][j + a[i]]) % mod;
if(j - a[i] >= 0) f[i][j] = (f[i][j] + f[i - 1][j - a[i]]) % mod;
}
f[i][B + a[i]]++,f[i][B - a[i]]++;
ans = (ans + f[i][B]) % mod;
}
printf("%d",ans);
return 0;
}