【DP계획】11.4--[BZOJ]역순 대수열(접두사 및 DP 최적화)EXTREMELY EASY
Output은 조건에 부합되는 수열의 개수를 표시하는 정수를 씁니다. 이 수가 매우 클 수 있기 때문에, 10000의 나머지 수를 출력하기만 하면 됩니다.
Sample Input 4 1 Sample Output 3
샘플 설명:
다음 세 개의 수열 역순 대수는 모두 1이다.각각 하나, 둘, 넷, 셋.1 3 2 4 ;2 1 3 4;
100% 데이터 n<=1000,k<=1000
우리는 이 배열을 어떻게 구축하는지 알기만 하면 된다.
만약 우리가 지금 1에서 n까지의 정렬을 가지고 있다면, 그것의 역정렬 대수는 0이다.그러면 왼쪽에서 오른쪽으로 매번 어떤 수를 왼쪽으로 x자리로 옮기면 x개의 역순이 생긴다.따라서 f[i][j]f[i][j]f[i][j]를 설정하면 현재 ii위에 도달했고 jj위를 왼쪽으로 이동한 방안수(즉 jjj개의 역순대 발생)를 나타낸다. 그러면 이동 방정식은
f[i][j]+=f[i-1][k] //k∈[j-i+1,j] ( i-1 i-2 )
그래서 직접 폭력 이전은 O(n3)O(n^3)O(n3)의 것이다.그러나 분명히 kk는 구간에 속하기 때문에 접두사와 최적화를 할 수 있고 f[i-3-1] f[i-1] f[i-3-1]에 대해 접두사와 최적화를 계산하면 된다.그리하여 복잡도는 O(n2)O(n^2)O(n2)
#include
#define MD 10000
using namespace std;
int read(){
char c;int x;while(c=getchar(),c'9');x=c-'0';
while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
int n,k,f[1005][1005],sum[1005];
int main()
{
n=read();k=read();
f[1][0]=1;for(int i=0;i<=k;i++) sum[i]=1;
for(int i=2;i<=n;i++){
f[i][0]=1;
for(int j=1;j<=k;j++){
int x=max(0,j-i+1)-1;
(f[i][j]+=sum[j]-sum[x])%=MD;
}
for(int j=0;j<=k;j++) sum[j]=sum[j-1]+f[i][j];
}
printf("%d",f[n][k]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ3930: [CQOI2015] 선택거의 짠 물고기일 거야.. 처음에 제목 yy에 대해 정확할 것 같고 복잡도 계산이 안 되는 검색을 했는데 잘 안 되는 것 같아서 DP를 생각하고 정확해 보이는 DP를 생각해서 끊었어요.그럼 용납하고 싶다......설...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.