UVA 12032 - The Monkey and the Oiled Bamboo(cpp file)

Problem Type : DP




#include<iostream>
#include<cmath>
#include<cstring>
#define MIN -2147483647;
using namespace std;

int main()
{
    int t,n,i,j,temp,sum,arr[100000],mi;
    cin >> t;
    for(i=1; i<=t; i++)
    {
        cin >> n;
        temp=0;
        arr[0]=0;
        for(j=1; j<=n; j++)
        {
            cin >> arr[j];

        }
        mi = MIN;
        for ( int i = 1; i <= n; i++ )
        {
            int diff = arr [i] - arr [i - 1];
            if ( diff > mi )
            {
                mi=diff;
            }

        }
        int res = mi;
        for ( int i = 1; i <= n; i++ )
        {
            int diff=arr [i] - arr [i - 1];
            if (diff==mi)
            {
                mi--;
            }
            else if(diff> mi)
            {
                res++;
                break;
            }
        }

        cout <<"Case "<<i <<": "<< res << endl;

    }
    return 0;
}