2016年9月2日 星期五

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;
   }
}

沒有留言:

張貼留言