NYOJ 279 팀 꽃의 고민 2와 NYOJ 176 정수 구분(二)[dp문제 또는 귀속]
이 두 문제의 뜻은 기본적으로 같다. 바로 테스트 데이터의 범위가 다르다는 것이다.176 데이터는 비교적 물적이어서 일반적으로 시간을 초과하지 않지만, 279를 사용하면 시간을 초과할 수 있다.간단하게 dp로 문제를 푸는 사고방식을 말해 봅시다.
먼저 f(i, j)를 정수 i로 정의하여 j개의 정수로 나누는 상황...
분석을 통해 얻을 수 있는 f(i, j)는 두 부분으로 바뀔 수 있다.
1: 분할된 j개의 정수에 1이 포함되지 않는다고 가정합니다.그러면 이때 f(i-j, j)가 바로 이 부분의 전체 상황입니다.알겠어요?좀 더 똑똑히 말해봐.기왕 그가 1을 포함하지 못하게 하려면 먼저 j개의 정수를 모두 1로 나눈다. 이때 i는 i-j로 변한 다음에 i를 j개의 정수로 나눈다. 이 j개의 정수에 원래 나눴던 1을 더하면 틀림없이 다시는 1이 나타나지 않을 것이다.오케이 했지?
2: 가설적으로 나누어진 j개의 정수는 적어도 1개의 1이 있다.그러면 이때 f(i-1, j-1)가 바로 이 부분의 전체 상황입니다.그건 알겠지?글쎄요. 직접 분석해보세요.
결론: f(i, j) = f(i-j, j)＋f(i-1, j-1).동적 이동 방정식이 생겼으니 실현하기가 어렵지 않겠지...참, 초기화에는 아직 약간의 기교가 있다.스스로 궁리하다.그리고 문제의 데이터 범위가 그리 넓지 않기 때문에 폭력적인 해답이 빠를 것이다...
279 코드:
#include<stdio.h>
int main()
{
int a,b,n,m,k;
int ok[505][7]={0};
ok[1][1]=1;
for(a=2;a<=500;a++)
{
for(b=1;b<=a&&b<=6;b++)
ok[a][b]=ok[a-b][b]+ok[a-1][b-1];
}
while(~scanf("%d%d",&n,&m))
{
printf("%d
",ok[n][m]);
}
}
#include<stdio.h>
int main()
{
int a,b,n,m,k;
int ok[105][105]={0};
ok[1][1]=1;
for(a=2;a<=100;a++)
{
for(b=1;b<=a;b++)
ok[a][b]=ok[a-b][b]+ok[a-1][b-1];
}
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&n,&m);
printf("%d
",ok[n][m]);
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
