This is a C++ Program that Solves Army Problem using Dynamic Programming technique.
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.
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.
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
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;
}
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.
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.
- Practice Programming MCQs
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Practice Design & Analysis of Algorithms MCQ
- Check Data Structure Books