题目:click here
:这个题可以先dfs深搜下,规律dp
dfs:
#include <bits/stdc++.h>
using namespace std;
#define S second
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int M = 1e5+; int s;
int cnt = ;
bool vis[];
void dfs( int last, int num ) {
if( num == s ) {
cnt++;
return ;
}
for( int i=; i<s+; i++ )
if( abs(last-i)<= && !vis[i] ) {
vis[i] = true;
dfs( i, num+ );
vis[i] = false;
}
}
int main() {
while( ~scanf("%d", &s ) ) {
memset( vis, false, sizeof(vis) );
cnt = ;
vis[] = true;
dfs( , );
printf("%d\n", cnt );
}
return ;
}
DP:
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef unsigned long long ll;
const int INF = 0x3f3f3f3f;
const int M = 1e5+; int s;
ll dp[];
void pre() {
memset( dp, , sizeof(dp) );
dp[] = ;
dp[] = ;
dp[] = ;
dp[] = ;
for( int i=; i<=; i++ )
dp[i] = dp[i-]+dp[i-]+;
}
int main() {
pre();
while( ~scanf("%d", &s ) ) {
printf("%I64d\n", dp[s] );
}
return ;
}