概述
传送门:点击打开链接
定义状态dp[i][j][0]表示以a[i],b[j]结尾的且为波谷的情况总和,dp[i][j][1] 为波峰。
对于某个i,j满足a[i] == b[j],则dp[i][j][0] = sum(dp[x][y][1]), x < i && y < j && b[y] > a[i]
设sum[i-1][y][1] = ∑dp[x][y][1] , x <= i-1
则dp[i][j][0] = ∑sum[i-1][y][1], b[y] > a[i]
对于每一个b[j],sum[i][j]累计了前i个的a[i]的影响,每次求出dp[i][j]后O(1)更新即可,即sum[i][j][1] =sum[i-1][j][1] + dp[i][j][1]。
然后对于某一个a[i]的所有b[j],可以以前缀和的形式,利用sum[i-1][y],O(n)全部更新。
所以复杂度O(nm)。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int MOD = 998244353;
const int N = 2005;
int a[N], n;
int b[N], m;
int dp[N][2];
int sum[N][2];
int main()
{
//freopen("test.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin.sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
LL ans = 0;
for (int i = 1; i <= n; i++)
{
int cnt1 = 0;
int cnt0 = 0;
for (int j = 1; j <= m; j++)
{
if (a[i] == b[j])
{
dp[j][0] = cnt1 + 1; // 因为波谷可以作为开头,所以自身算一种。
dp[j][1] = cnt0;
ans = (ans + cnt0 + cnt1 + 1) % MOD;
}
else if (b[j] > a[i])
cnt1 = (cnt1 + sum[j][1]) % MOD;
else
cnt0 = (cnt0 + sum[j][0]) % MOD;
}
for (int j = 1; j <= m; j++)
if (a[i] == b[j])
{
sum[j][0] = (sum[j][0] + dp[j][0]) % MOD;
sum[j][1] = (sum[j][1] + dp[j][1]) % MOD;
}
}
cout << ans << endl;
}
return 0;
}
最后
以上就是昏睡月饼为你收集整理的(2017多校训练第四场)HDU - 6078 Wavel Sequence dp的全部内容,希望文章能够帮你解决(2017多校训练第四场)HDU - 6078 Wavel Sequence dp所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复