(2017 멀티 스쿨링 4차전) HDU - 6078 Wavel Sequence dp
2092 단어 ACM - 기본 dp
정의 상태 dp[i][j][0]는 a[i], b[j]로 끝나는 파곡의 상황을 총화하고 dp[i][j]는 파봉이다.
어떤 i에 대해 j가 a[i]=b[j]를 만족시키면 dp[i][j][0]=sum(dp[x][y][1]), x 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
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
(2017 멀티 스쿨링 4차전) HDU - 6078 Wavel Sequence dp전송문:클릭하여 링크 열기 정의 상태 dp[i][j][0]는 a[i], b[j]로 끝나는 파곡의 상황을 총화하고 dp[i][j]는 파봉이다. 어떤 i에 대해 j가 a[i]=b[j]를 만족시키면 dp[i][j][0]=...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
