UVA 10559 Blocks

主题素材轮廓:有生机勃勃串带颜色的四方,每趟能够消掉颜色相像的意气风发段,得到size^2的分数,问最多能获得多少分数。n≤200。

给那题状态跪下来。

分明性的间隔DP,但设f[i][j]是相当不够的。

假造到事先做过的题,于是强制一下右端点,设成三维f[i][j][k],k表示什么吧?

若有若无推到了笔录和右端点雷同的水彩,但要么不能够总括,离正解最后依然差了一步。

记f[i][j][k]表示将间隔[i,j],j左侧加上k个与区间右端点颜色相似的块清空的最大得分。

是的,区间DP设之处跟外部的条件有关。

干什么要如此设?其实自个儿不领会。

自家前边是这样思忖的:记录内部最后有k个与右端点相近还未有被消掉的,不过那几个k完全不能够总括。

可是你记录外面包车型客车景况,就无须管,因为你管理的主意分明是回想搜,不会有结余情状被搜到。

之所以那题正是乐于助人设状态,脑洞清奇。

转移方程研究一下,直接消/把最终四个的颜色前边者颜料同样的一齐拍卖,中间生机勃勃节扣出来。

图片 1图片 2

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
#define FILE "10559"
using namespace std;

const int N = 221;
int n,A[N],f[N][N][N];

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline int dfs(int i,int j,int k,register int r=0){
  if(f[i][j][k])return f[i][j][k];
  for(r=j;r>=i && A[r]==A[j];--r);int p=(k+j-r)*(k+j-r);
  if(r<i)return f[i][j][k]=p;f[i][j][k]=dfs(i,r,0)+p;
  for(register int l=r;l>=i;--l)
    if(A[l]==A[j])
      f[i][j][k]=max(f[i][j][k],dfs(i,l,k+j-r)+dfs(l+1,r,0));
  return f[i][j][k];
}

inline void solve(){
  n=gi();memset(f,0,sizeof(f));
  for(int i=1;i<=n;++i)A[i]=gi();
  for(int i=1;i<=n;++i)
    for(int j=0;j<n;++j)
      f[i][i][j]=(j+1)*(j+1);
  printf("%d\n",dfs(1,n,0));
}

int main()
{
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
  int Case=gi();
  for(int t=1;t<=Case;++t){
    printf("Case %d: ",t);
    solve();
  }
  fclose(stdin);fclose(stdout);
  return 0;
}

Blocks