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:

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

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.

Check this: Data Structure Books | Computer Science Books

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

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Apply for Information Technology Internship
Practice Computer Science MCQs
Buy Programming Books
Buy Data Structure Books
Practice Programming MCQs

Recommended Articles: