2019 멀티 스쿨 1차전 HDU6578 - Blank(DP, 사고, 스크롤 배열 최적화 공간)
제목:
n(≤100)개의 칸이 있고, 그 중에서 0, 1, 2, 3 등 4개의 수를 채우지만, m(≤100)개의 제한이 있다.
lrx 제한: l~r의 칸 안의 다른 수를 나타내는 개수는 x이다
-- 모두 몇 가지 채움안이 있나.
분석:
구축 dp[i][j][k][t][cur]: i, j, k, t는 각각 0,1,2,3이 나타나는 마지막 위치를 나타내고cur는 첫 번째cur칸에 기입한 것을 나타낸다.
이미 구한 dp[i][j][t] [t] [cur-1]는 다음 상태 전이 방정식 (다음 순서 0, 1, 2, 3): d p [c u] [j] [k] [t] [t] [t] [t] [c ur] = d p [c ur] [j] [k] [k] [t] [t] [cur] + d p [i] [j] [j] [k] [k] [k] [k] [k] [k] [k] [k] [k] [k] [k] [k] [u] [c] [u] [c] [u] [u] [k] [u] [k] [u] [k] [u] [k] [u] [k] [u] [u] [u] [u] [u] [+ d p [i] [j] [k] [t] [c u r -3 1] d p [i] [j][ c u r ] [ t ] [ c u r ] = d p [ i ] [ j ] [ c u r ] [ t ] [ c u r ] + d p [ i ] [ j ] [ k ] [ t ] [ c u r − 1 ] d p [ i ] [ j ] [ k ] [ c u r ] [ c u r ] = d p [ i ] [ j ] [ k ] [ c u r ] [ c u r ] + d p [ i ] [ j ] [ k ] [ t ] [ c u r − 1 ] dp[cur][j][k][t][cur]=dp[cur][j][k][t][cur]+dp[i][j][k][t][cur-1]\\dp[i][cur][k][t][cur]=dp[i][cur][k][t][cur]+dp[i][j][k][t][cur-1]\\dp[i][j][cur][t][cur]=dp[i][j][cur][t][cur]+dp[i][j][k][t][cur-1]\\dp[i][j][k][cur][cur]=dp[i][j][k][cur][cur]+dp[i][j][k][t][cur-1] dp[cur][j][k][t][cur]=dp[cur][j][k][t][cur]+dp[i][j][k][t][cur−1]dp[i][cur][k][t][cur]=dp[i][cur][k][t][cur]+dp[i][j][k][t][cur−1]dp[i][j][cur][t][cur]=dp[i][j][cur][t][cur]+dp[i][j][k][t][cur−1]dp[i][j][k][cur][cur]=dp[i][j][k][cur][cur]+dp[i][j][k][t][cur−1]
이렇게 하면 모든 제한에 대해cur==r일 때 0,1,2,3에 따라 나타나는 마지막 위치 i,j,k,t가 >=l인지 여부에 따라 몇 개의 다른 수를 얻어낼 수 있다. 만약에 x와 같지 않으면 dp값은 0이 된다.
공간 복잡성 O(N5), 시간 복잡성 O(N5)
시간과 공간의 복잡도가 모두 5방에 이르렀으니 최적화를 해야 한다.
최적화 ①
i, j, k, t는 어떤 수가 마지막으로 나타난 위치를 표시하기 때문에 반드시 하나는cur와 같고 서로 같지 않다(0이 아니면 채워지지 않았다)
그러면 dp[i][j][k][cur]를 구축할 수 있다. 그 중에서 i
이렇게 하면 시간 복잡도와 공간 복잡도가 모두 O(N4)로 최적화되고 시간은 겨우 괜찮지만 공간은 여전히 너무 크다.
최적화 ②
dp[][][][cur]는 사실 dp[][][][cur-1]와만 관련이 있는 것을 발견할 수 있다. 그러면 스크롤 그룹으로 공간을 절약할 수 있다.
구축 dp[i][j][k][2],상태 전이 방정식: d p [j] [k] [c u r 1, 1] [n o w] = d p [j] [k] [k] [c u r 1] [n o w w w + d p [i] [j] [k] [k r e] d p [i] [k] [k] [c u r - 1] [n o w w] [d p [i] [k] [k] [k] [k] [c u r r r - 1] [n o w w w] [i] [k] [k] [k] [k] [k] [k] [k]] p p r r e e e e e e e e]] p i i = d d d w w w w w w w w w w w w w w w w w w w w w w w w w w w w w w w w i] [j] [c u r -3 1] [n o w] + d p [i] [j] [k] [p r e] d p [i][ j ] [ k ] [ n o w ] = d p [ i ] [ j ] [ k ] [ n o w ] + d p [ i ] [ j ] [ k ] [ p r e ] dp[j][k][cur-1][now]=dp[j][k][cur-1][now]+dp[i][j][k][pre]\\dp[i][k][cur-1][now]=dp[i][k][cur-1][now]+dp[i][j][k][pre]\\dp[i][j][cur-1][now]=dp[i][j][cur-1][now]+dp[i][j][k][pre]\\dp[i][j][k][now]=dp[i][j][k][now]+dp[i][j][k][pre]\\dp[j][k][cur−1][now]=dp[j][k][cur−1][now]+dp[i][j][k][pre]dp[i][k][cur−1][now]=dp[i][k][cur−1][now]+dp[i][j][k][pre]dp[i][j][cur−1][now]=dp[i][j][cur−1][now]+dp[i][j][k][pre]dp[i][j][k][now]=dp[i][j][k][now]+dp[i][j][k][pre]
주의: 여기는 누적이기 때문에 스크롤 그룹을 사용할 때 dp[i][j][k][pre]를 다 쓴 후에 비워야 합니다!
최종 공간 복잡성은 O(2*N3), 시간 복잡성 O(N4)
다음 코드:
#include
for(int i=0;i<max(j,1);i++)
{
dp[j][k][cur-1][now]=(dp[j][k][cur-1][now]+dp[i][j][k][pre])%MOD;
dp[i][k][cur-1][now]=(dp[i][k][cur-1][now]+dp[i][j][k][pre])%MOD;
dp[i][j][cur-1][now]=(dp[i][j][cur-1][now]+dp[i][j][k][pre])%MOD;
dp[i][j][k][now]=(dp[i][j][k][now]+dp[i][j][k][pre])%MOD;
dp[i][j][k][pre]=0; //
}
for(int k=0;k<max(cur,1);k++)
for(int j=0;j<max(k,1);j++)
for(int i=0;i<max(j,1);i++)
{
for(int p=0;p<lim[cur].size();p++)
{
PII t=lim[cur][p]; //cur [l,r]
if((i>=t.first)+(j>=t.first)+(k>=t.first)+1!=t.second)
dp[i][j][k][now]=0;
}
}
swap(now,pre);
}
// cur==n dp ，
LL ans=0;
for(int k=0;k<max(n,1);k++)
for(int j=0;j<max(k,1);j++)
for(int i=0;i<max(j,1);i++)
ans=(ans+dp[i][j][k][pre])%MOD; // now pre ， pre
printf("%lld
",ans);
}
return 0;
}
좋은 웹페이지 즐겨찾기
