Algorithm


problem Link  : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1461 

Consider that ai,j is defined as:

ai,j =

{

maxi<k≤n(ak,1 + ak,j ) , i < n

0 , i = n

+

{

max1≤k 0

0 , j = 0 , i ≥ j

maxi≤k

You are to calculate the value of a1,n on the basis of the values of n and an,1.

Input

The input consists of several test cases. Each Test case consists of two integers n (0 < n < 20) and

an,1 (0 < an,1 < 500).

Output

For each test case your correct program should print the value of a1,n in a separate line.

Sample Input

5 10

4 1

6 13

Sample Output

1140

42

3770

Code Examples

#1 Code Example with C Programming

Code - C Programming

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,v;
    while(scanf("%d %d",&n,&v) != EOF){
        long long a[50][50] = {};
        a[n][1] = v;
        for(int i=n; i>= 1; i--){
            for(int j=1; j < =n; j++){
                if(j==1 && i==n)
                    continue;
                if(i>=j){
                    long long left = 0, right = 0;
                    for(int k=i+1;k i+It =n;k++)
                        left = max(a[k][1]+a[k][j], left);
                    for(int k=1;k i+It j;k++)
                        right = max(a[i][k]+a[n][k],right);
                    a[i][j] = left+right;
                } else {
                    for(int k=i;k i+It j;k++)
                        a[i][j] = max(a[i][k]+a[k+1][j],a[i][j]);
                }
            }
        }
        printf("%lld\n",a[1][n]);
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
5 10
4 1
6 13

Output

x
+
cmd
1140
42
3770
Advertisements

Demonstration


UVA Online Judge solution -10520-Determine it - UVA Online Judge solution in C,C++,java 

Previous
UVA Online Judge solution - 10509-R U Kidding Mr. Feynman? -UVA Online Judge solution in C,C++,java
Next
UVA Online Judge solution - 10523-Very Easy !!!.java - UVA Online Judge solution in C,C++,java