[HDU4899] [2014 복수 학교 연합 시험4] Hero meet devil [LCS] [상태 압축] [dp 끼워넣기]
제목: DNA 꼬치 S를 주세요.각 i≤|S|에 대해 길이가 M이고 직렬 S의 가장 긴 공통 서열 길이가 i인 DNA 직렬 T를 구한다.결과mod 1e9+7. |S|≤15, M≤1000
15(경각심)자연의 생각은 LCS를 매거한 다음에 dp를 누르는 것을 고려하는 것이다.dp에서 진짜인지 아닌지 판단할 때그런데 이렇게
LCS 길이나 끝 위치를 저장하면 충돌이 발생할 수 있습니다. (같은 상태가 다르고 충돌이 발생할 수 있습니다.)후효성을 없애려면 현재 처리된 T의 마지막 비트와 S의 모든 비트의 일치 상태를 기록해야 한다.그러나 n2lcs는 온라인으로 구할 수 있음을 감안하여lcs와 상태를 압합할 수 있다.
n2LCS 구법을 되돌아보다.F(i, j) = max {F(i, j-1), F(i-1, j), F(i-1, j-1) + (Si==Tj)} j를 온라인으로 사용할 수 있습니다.그래서 상압 dp에 끼워넣을 수 있어요.구체적인 방식은 상압 안에 현재 LCS에서 어디에 일치하는지 기록하는 것이다. 이 위치에 어떤 문자를 넣으면 LCS의 길이가 어떻게 이동하는지 미리 처리하는 것이다.
위에는 대략적인 사고방식일 뿐이고 실현할 때 많은 세부 사항이 있으니 반드시 주의해야 한다.
#include
#include
#include
#include
using std::cin;
using std::cout;
using std::endl;
using std::string;
const int mod = 1000000007;
int nLim;
int nLenSrc;
int nLenTar;
int nLenBef[20];
int nLenAft[20];
int nTransSrc[20];
int nMap[26];
int nNxt[32780][4];
int nDiff[2][32780];
int ans[20];
string strSrc;
void input() {
cin >> strSrc >> nLenTar;
}
void init() {
memset(nDiff, 0, sizeof(nDiff));
memset(ans, 0, sizeof(ans));
nLenSrc = strSrc.size();
nLim = (1 << nLenSrc) - 1;
for (register int i = 1; i <= nLenSrc; ++i) nTransSrc[i] = nMap[strSrc[i-1]-'A'];
for (register int i = 0; i <= nLim; ++i) {
memset(nLenBef, 0, sizeof(nLenBef));
for (register int j = 1; j <= nLenSrc; ++j) nLenBef[j] = nLenBef[j-1] + ((i>>j-1)&1);
for (register int k = 0; k < 4; ++k) {
for(register int j = 1; j <= nLenSrc; ++j) {
nLenAft[j] = std::max(nLenAft[j-1], nLenBef[j]);
if (nTransSrc[j] == k) nLenAft[j] = std::max(nLenAft[j], nLenBef[j-1] + 1);
}
nNxt[i][k] = 0;
for (register int j = 1; j <= nLenSrc; ++j)
if (nLenAft[j] ^ nLenAft[j-1]) nNxt[i][k] |= 1 << j - 1;
}
}
}
int calc(int x) {
int ret = 0;
while (x) {
ret += x & 1;
x >>= 1;
}
return ret;
}
void work() {
nDiff[0][0] = 1;
bool parity;
for (register int i = 1; i <= nLenTar; ++i) {
parity = i & 1;
memset(nDiff[parity], 0, sizeof(nDiff[parity]));
for (register int j = 0; j <= nLim; ++j) {
for (register int k = 0; k < 4; ++k) {
nDiff[parity][nNxt[j][k]] += nDiff[!parity][j];
nDiff[parity][nNxt[j][k]] %= mod;
}
}
}
for (register int t, i = 0; i <= nLim; ++i)
{
t = calc(i);
ans[t] += nDiff[parity][i];
ans[t] %= mod;
}
}
void output() {
for (register int i = 0; i <= nLenSrc; ++i) {
cout << ans[i] << endl;
}
}
int main() {
std::ios::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
nMap['A'-'A'] = 0;
nMap['C'-'A'] = 1;
nMap['G'-'A'] = 2;
nMap['T'-'A'] = 3;
int nTestCases;
cin >> nTestCases;
for (register int i = 1; i <= nTestCases; ++i) {
input(); init(); work(); output();
}
return 0;
}
한나절 동안 간단히 썼는데
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.