UVa 11554 - Hapless Hedonism

Problem link

Keyword: DP, geometry

Algorithm:


The number of methods using sticks up to N cm is the number of methods of N-1 cm plus the number of methods using an N cm stick. (Because if we have sticks up to N cm, we can choose to or not to use the N-th stick.)
For example, for N=10, we can choose not to use the 10-cm stick and we have answer when N=9. Then we can use the 10-cm stick and calculate how many ways can be used. This is actually a summation problem and we can find a formula for this.

Code:

#include<cstdio>
int t, n;
long long int ans[ 1000001 ] = { 0 };

int main()
{
    for( long long int i = 4; i <= 1e6; ++i )
        ans[ i ] = ans[ i-1 ] + ( ( i+1 ) % 2 + i-3 ) * ( ( i-1 ) / 2 ) / 2;
    scanf( "%d", &t );

    while( t-- )
    {
        scanf( "%d", &n );
        printf( "%lld\n", ans[ n ] );
    }

    return 0;
}