계단 문제: 점차적 + 최적화

제목 링크: 간략한 버전의 제목:noi문제집 3525단계 문제 본고는 주로 사고방식1이 점차적으로 추진되는 소박한 사고방식 O(n*k)의 상응하는 해법과 코드를 소개한다.사고방식2 점차적으로 O(n)의 상응하는 분석과 코드를 최적화한다.또한 기억화 귀환도 있고 데이터를 확장한 후의 행렬 곱셈도 있어 관심 있는 학생들은 스스로 갈 수 있다.
제목 대의: 1 계단을 올라갈 때 매번 1-k급을 올라갈 수 있고 지면에서부터 n급까지 올라갈 수 있다. 몇 가지 방안이 있는가.
문제풀이 사고방식1: 소박하고 직관적: O(n*k)1 현재 x급이면 x-1, x-2, x-3에서...x-k, 이 k급 계단이 올라오기 때문에 이중순환으로 매거하면 된다.2 디테일에 주의해야 할 것은 계단은 0에서 시작하여 마이너스가 없다는 것이다.3 모형을 추출하는 것을 기억한다.위 코드:

//luogu1192:    ：      
//     ：n*k 

#include
#define mo 100003
using namespace std;
int n,k,ans=0;
int f[100005];

int main()
{
	scanf("%d %d",&n,&k);
	memset(f,0,sizeof(f));
	f[0]=f[1]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=max(0,i-k);j

문제풀이 사고방식 2: 관찰 분석과 선형 최적화: O(n)1은 다음과 같은 세 마디를 관찰한다. 현재는 x급이고 x-1, x-2, x-3에서...x-k+2, x-k+1, x-k, 이 k급 계단을 올라오기;현재는 x+1레벨입니다. x, x-1, x-2, x-3에서...x-k+2, x-k+1, 이 k급 계단 올라오기;현재 x+2 레벨, x+1, x, x-1, x-2, x-3에서...x-k+2, 이 k급 계단 올라오기;2 두 번 인접한 많은 연산이 교차하는 것을 발견했는가?3 그리고 다음과 같은 간단한 추산 과정을 얻어낼 수 있다.
식1:a[x]=a[x-1]+a[x-2]+...+a[x-k+1]+a[x-k] ; 식자2:a[x+1]=a[x]+a[x-1]+a[x-2]+...+a[x-k+1] ;
식자1과 식자2에서 식자3:a[x+1]=a[x]*2-a[x-k]를 얻을 수 있다.
식자 3을 한 단계 낮추면 다음과 같이 추산할 수 있다. a[x]=a[x-1]*2-a[x-k-1](x>k일 때 성립)
4x(x-1)의 계단이 x까지 올라갈 수 있기 때문에:
식1:a[x]=a[x-1]+a[x-2]+...+a[0] ; 식자2:a[x+1]=a[x]+a[x-1]+a[x-2]+...+a[0] ;
식자1과 식자2에서 식자3:a[x+1]=a[x]*2를 얻을 수 있다.
식자3을 한 단계 낮추면 다음과 같이 추산할 수 있다. a[x]=a[x-1]*2(x<=k일 때 성립)
5 연산 과정에 마이너스가 있기 때문에 마지막에 마이너스 배제를 해야 한다.
위 코드:

//luogu1192    ：  +  
//     O(n) 
//    ，       k         
//     ，            
 
#include
#define mo 100003
using namespace std;
int n,k,ans=0;
int a[100005];

int main()
{
	scanf("%d %d",&n,&k);
	a[0]=a[1]=1;
	
	for(int i=2;i<=k;i++)
	{
		a[i]=a[i-1]*2%mo;
	}
	for(int i=k+1;i<=n;i++)
	{
		a[i]=a[i-1]*2-a[i-k-1];
		a[i]%=mo;
	}
	
	printf("%d",(a[n]+mo)%mo);//     
	
	return 0;
}