PKU 1390-Blocks

PKU

問題概要

ある数列が与えられる。
同じ数字が並んでいるとき、その個数の二乗だけ得点が入り、その得点になった分の数字は消滅する。
得点の最大値を求めよ。

考え方

ある区間の最大の得点をメモ化再帰で求めていく。

実装(C++)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
pair<int,int> in[200];
int n,memo[200][201][201];
int solve(int s,int e,int cnt=0){
  if(s>=e)return 0;
  if(memo[s][e][cnt]>=0)return memo[s][e][cnt];
  int ans=(cnt+in[s].second)*(cnt+in[s].second)+solve(s+1,e);
  for(int x=s+1;x<e;x++)if(in[s].first==in[x].first)ans=max(ans,solve(s+1,x,0)+solve(x,e,cnt+in[s].second));
  return memo[s][e][cnt]=ans;
}
int main(int tcase){
  int m,back,d;
  for(scanf("%d",&m);~scanf("%d",&m);tcase++){
    n=0;back=0;
      for(int i=0;i<m;i++){
        scanf("%d",&d);
        if(n&&in[n-1].first==d)in[n-1].second++;else in[n++].first=d,in[n-1].second=1;
      }
      memset(memo,-1,sizeof(memo));
      printf("Case %d: %d\n",tcase,solve(0,n));
  }
  return 0;
}