Army Problem - Dynamic Programming Solutions

This is a C++ Program that Solves Army Problem using Dynamic Programming technique.

Problem Description

The Berland Armed Forces System consists of n ranks that are numbered using natural numbers from 1 to n, where 1 is the lowest rank and n is the highest rank.

One needs exactly d[i] years to rise from rank i to rank i + 1. Reaching a certain rank i having not reached all the previous i - 1 ranks is impossible.

Vasya has just reached a new rank of a, but he dreams of holding the rank of b. Find for how many more years Vasya should serve in the army until he can finally realize his dream.

Problem Solution

In this problem, we will simply find total number of years required to reach rank a from rank 1, then total number of years required to rise from rank 1 to rank b. For this we will maintain a commulative array sum, where sum[i]=total number of years required to rise from rank 1 to rank i. Once we have initialized this array, the answer to our question will be the difference of these two values.

Expected Input and Output

Case-1:

Number of ranks in the army= 3
Number of years required to rise from previous rank to next rank for every rank= {5, 6}
Initial rank=1  
Targer rank=2
Number of years required to rise from rank 1 to rank 2 are = 5

Program/Source Code

Here is source code of the C++ Program to Solve Army Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
 
```
```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
int main()
```
```
{
```
```
    int i,j;
```
```
    int n;
```
```
    int x,y;
```

    cout<<"Enter the number of ranks in the army ";

```
    cin>>n;
```
```
    vector<int> sum(n);
```
```
    sum[0]=0;
```
```
 
```

    cout<<"Enter the number of years required to rise from previous rank to next rank for every rank"<<endl;

```
    for(i=0;i<n-1;i++)
```
```
    {
```
```
        cin>>x;
```
```
        sum[i+1]=sum[i]+x;
```
```
    }
```
```
 
```
```
    cout<<"Enter the initial rank  ";
```
```
    cin>>x;
```
```
    cout<<"Enter the targer rank ";
```
```
    cin>>y;
```

    cout<<"Number of years required to rise from rank "<<x<<" to rank "<<y<<"are"<<endl;

```
    cout<<sum[y-1]-sum[x-1]<<endl;
```
```
 
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask user to input the values for number of ranks, and years required for transition. We prepare a commulative array sum[i] based on this data. Then we ask the ask the user for its initial and final rank. Then, the corresponding result is displayed.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Runtime Test Cases

 
Case-1:
$ g++ army.cpp
$ ./a.out
Enter the number of ranks in the army 3
Enter the number of years required to rise from previous rank to next rank for every rank
5 6
Enter the initial rank  1  
Enter the targer rank 2
Number of years required to rise from rank 1 to rank 2are
5

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Trigraphs Problem using Dynamic Programming

» Next - Boredom Problem – Dynamic Programming Solutions

Related Posts:

Practice Programming MCQs
Practice Computer Science MCQs
Apply for Computer Science Internship
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books

Recommended Articles: