Light OJ 1283 / DP - Interval

/***
 created: 2022-09-21-03.18.37
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll dp[101][101][101];
ll a[102],n;

ll solve(ll in,ll l,ll r)
{
    if(in>n) return 0;

    if(dp[in][l][r]!=-1) return dp[in][l][r];

    ll ans=solve(in+1,l,r);

    if(a[in]>=a[l] && a[in]<=a[r])
    {
        ans=max(ans,max( solve(in+1,in,r)+1, solve(in+1,l,in)+1 ));
    }
    return dp[in][l][r]=ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    test
    {
        ll i,j,k,l;

        cin>>n;

        for(i=1;i<=n;i++) cin>>a[i];

        memset(dp,-1,sizeof dp);

        a[0]=0;
        a[n+1]=1e15;

        cout<<"Case "<<cs<<": "<<solve(1,0,n+1)<<nl;
    }


    get_lost_idiot;
}