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]);
}
}
Input
5 10
4 1
6 13
4 1
6 13
Output
1140
42
3770
42
3770
Demonstration
UVA Online Judge solution -10520-Determine it - UVA Online Judge solution in C,C++,java