DP URAL 1260 Nudnik Photographer

 1 /*  2    DP: dp[i]    i    ，     n-2         3 */  4 #include <cstdio>  5 #include <algorithm>  6 #include <cmath>  7 #include <cstring>  8 using namespace std;  9 10 const int MAXN = 1e4 + 10; 11 const int INF = 0x3f3f3f3f; 12 int dp[60]; 13 14 int main(void) //URAL 1260 Nudnik Photographer 15 { 16 //freopen ("G.in", "r", stdin); 17 18 int n; 19 while (scanf ("%d", &n) == 1) 20  { 21 memset (dp, 0, sizeof (dp)); 22 dp[1] = 1; 23 for (int i=2; i<=n; ++i) 24  { 25 dp[i] = dp[i-1]; 26 if (i > 3) 27  { 28 dp[i] += dp[i-3]; 29  } 30  } 31 32 long long ans = dp[n]; 33 if (n > 2) 34  { 35 for (int i=1; i<=n-2; ++i) ans += dp[i]; 36  } 37 printf ("%I64d
", ans); 38  } 39 40 return 0; 41 }