傳送門：點擊打開鏈接

定義狀態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;elsecnt0 = (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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。