UVA 10559 - Blocks

UVA 10559 - Blocks

題目概述:入門經典書p9-55

待補QQ

思路:

待補QQ

//By SCJ

//#include<iostream>

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define INF 1000000000

int a[205],dp[205][205][205],lapos[205];

int d(int i,int j,int k)

{

   if(i==lapos[j]) return dp[i][j][k]=(j-i+1+k)*(j-i+1+k);

   if(dp[i][j][k]!=-1) return dp[i][j][k];

   int p=lapos[j];

   dp[i][j][k]=d(i,p-1,0)+(j-p+1+k)*(j-p+1+k);

   for(int q=lapos[j]-1;q>=i;--q)

   {

       if(a[q]==a[j])

           dp[i][j][k]=max(dp[i][j][k],d(q+1,p-1,0)+d(i,q,k+j-p+1)),q=lapos[q];

   }

   return dp[i][j][k];

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   int T;cin>>T;

   for(int no=1;no<=T;++no)

   {

       memset(dp,-1,sizeof(dp));

       int n;cin>>n;

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

       int la=lapos[1]=1;

       for(int i=2;i<=n;++i)

       {

           if(a[i]!=a[i-1]) la=i;

           lapos[i]=la;

       }

       lapos[n]=la;

       cout<<"Case "<<no<<": "<<d(1,n,0)<<endl;

   }

}