BC의 The mook jong
ZJiaQ want to become a strong man, so he decided to play the mook jong.ZJiaQ want to put some mook jongs in his backyard. His backyard consist of n bricks that is 1*1,so it is 1*n.ZJiaQ want to put a mook jong in a brick. because of the hands of the mook jong, the distance of two mook jongs should be equal or more than 2 bricks. Now ZJiaQ want to know how many ways can ZJiaQ put mook jongs legally(at least one mook jong). Input
There ar multiply cases. For each case, there is a single integer n( 1 < = n < = 60) Output
Print the ways in a single line for each case. Sample Input
1 2 3 4 5 6
Sample Output
1 2 3 5 8 12
점차적으로 미루어 끝내다.공식 문제풀이: f[i]를 마지막 말뚝으로 i위치에 놓는 방안, s[i]를 f[i]의 접두사로 한다.쉽게 f[i]=s[i-3]+1, s[i]=s[i-1]+f[i]를 생각할 수 있고 s[n]는 바로 원하는 답이다.이 문제의 유일한 주의할 점은 n이 60에 가까워지면 int가 터진다는 것이다.
시작할 때 n당 몇 개를 넣을 수 있는지 고민하여 그룹(1, 2, 3, 4...)을 나누면 도무지 규칙을 찾을 수 없다.당시에 A가 사용했을 때도 점차적으로 밀어주는 방식으로 첫 번째를 첫 번째 위치에 놓고 나머지는 나머지 i-3 위치에만 놓을 수 있었다(이 i-3 위치에 도대체 몇 개를 넣었는지 신경 쓰지 않아도 된다)=a[i-3].두 번째 위치에서 나머지 i-4 위치에 = a[i-4]를 놓고 한 번 유추합니다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define rd(a) scanf("%d",&a)
#define rdLL(a) scanf("%I64d",&a)
#define rdd(a,b) scanf("%d%d",&a,&b)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)
#define MOD 1000000007
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,1,sizeof(a))
typedef pair<int , int> P;
int main()
{
LL a[100];
int n;
a[1]=1,a[2]=2,a[3]=3;
LL sum=1,coun=2;
for(int i = 4;i<61;i++)
a[i]=sum+i,sum+=a[coun++];
while( ~rd(n) ){
printf("%I64d
",a[n]);
}
return 0;
}