// http://acm.timus.ru/problem.aspx?space=1&num=1017
// Runtime: 0.078s
// Tag: Dp
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000005
#define LL long long
#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)
int dr [] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dc [] = {0, 1, 1, 1, 0, -1, -1, -1};
using namespace std;
LL memo [500 + 5] [500 + 5];
void reset ()
{
for ( int i = 0; i < 505; i++ )
for ( int j = 0; j < 505; j++ ) memo [i] [j] = -1;
}
LL dp (int prev, int remain)
{
if ( remain == 0 ) return 1;
if ( remain <= prev ) return 0;
if ( memo [prev] [remain] != -1 ) return memo [prev] [remain];
LL ret = 0;
for ( int i = prev + 1; i <= remain; i++ ) ret += dp (i, remain - i);
return memo [prev] [remain] = ret;
}
int main ()
{
int n;
while ( scanf ("%d", &n) != EOF ) {
reset ();
printf ("%lld\n", dp (0, n) - 1);
}
return 0;
}
// @END_OF_SOURCE_CODE

### Like this:

Like Loading...

*Related*

## Published by Shahab

Completed B.Sc in CSE, @United International University, Dhaka.
Currently working as Development Engineer, Android and iOS Application.
View all posts by Shahab

thanks dude, your code is easy to understand.

It helps me so much 🙂

Could you please explain this algorithm ? Thanks in advance

@NS

at first you need to understand dp problems and solving criteria

u can take help from topcoder algorithms tutorial

if you how to apply dp then here is the hints:

line 51:

prev = number of bricks you have set on previous column

remain = number of remaining bricks

line 53:

if remain = 0, then you have got a solution

line 54:

if remain <= prev, then you cant get a solution

line 56:

if you had come to this point before then don't calculate one more time, just return the previous calculated result

line 60:

now u r trying to fill up the current column with every possible number of bricks

obviously started from prev + 1 to <= remain

line 71:

prev = 0

remain = n

dp (0, n) gives the final result

but solutions with one column not acceptable

so we subtracted 1 from the final result

Why do you need a different remain state. We can easily say that remain is n-prev. Can you explain please?