LightOJ 10047 solution & CPP code

Its a dp problem.
Keep on counting minimum possible cost for each position. Use previous value to avoid calculating same thing again and again.

#include<stdio.h>
#define MIN(a,b) a<b? a:b
#define inf 99999999


int main()
{

    int fc,cost[22][5],a[22][5],i,j,n,t,kase,x,y;
    scanf("%d",&t);
    kase=0;
    while (kase++<t)
    {

        scanf("%d",&n);


        for (i=1;i<=n;i++)
            for (j=1;j<=3;j++)
                scanf("%d",&a[i][j]);


        cost[1][1]=a[1][1];
        cost[1][2]=a[1][2];
        cost[1][3]=a[1][3];

        for (i=2;i<=n;i++)
            {
                cost[i][1]=cost[i-1][2]+a[i][1];
                cost[i][1]=MIN(cost[i][1],cost[i-1][3]+a[i][1]);

                cost[i][2]=cost[i-1][1]+a[i][2];
                cost[i][2]=MIN(cost[i][2],cost[i-1][3]+a[i][2]);

                cost[i][3]=cost[i-1][2]+a[i][3];
                cost[i][3]=MIN(cost[i][3],cost[i-1][1]+a[i][3]);

            }
        fc=inf;
        for (i=1;i<=3;i++)
            fc=MIN(fc,cost[n][i]);

        printf("Case %d: %d\n",kase,fc);

    }

    return 0;
}

UVA 10446 solution & C++ code

ALGORITHM:

This is an DP problem.

Rather than calculating the value for a particular n and back u store it and when needed dont recalculte.

#include<stdio.h>

unsigned long long dp[70][70];

int ini()
{

    for (int i=0;i<70;i++)
        for (int j=0;j<70;j++)
            dp[i][j]=-1;

    return 0;
}

unsigned long long trib(int n,int back)
{


    if(n<=1)return 1;

    if (dp[n][back]!=-1)return dp[n][back];

    dp[n][back]=1;

    for (int i=1;i<=back;i++)
    {

        dp[n][back]+=trib(n-i,back);
    }
    return dp[n][back];

}


int main(void)

{
    int n,back,kase=1;;


    while (1)
    {

        scanf("%d%d",&n,&back);

        if (n>60)break;

        ini();

        printf("Case %d: %llu\n", kase++,trib(n,back));
    }
    return 0;

}

 Algorithm:There are 2 possible arrangements for maximum size of 4-squares for a given size of paper
X X
X X

AND

X X X X

Thus, we get the formula:
let l = longer side of the rectangular paper
let s = shorter side of the rectangular paper
max square size = MAX(MIN(l/4.0, s), s/2.0)

Iterate through the answer and search for the first maximum.



Code:

#include<stdio.h>

#define MAX(a,b) (((a) > (b)) ? (a) : (b))

#define MIN(a,b) (((a) < (b)) ? (a) : (b))

int main(){

int i,n,num;

float l,s,tmp,size,mmm;



while(scanf("%d",&n)&&n){

mmm=0;

for(i=1;i<=n;i  ){

scanf("%f %f",&l,&s);

if(l<s) {

tmp=l;

l=s;

s=tmp;

}

size= MAX(MIN(l/4, s), s/2);

if(size>mmm) {mmm=size;num=i;}







}

printf("%d\n",num);





}

return 0;

}