区间DP（POJ 1390）

Blocks

Description

Some of you may have played a game called 'Blocks'. There are n blocks in a row, each box has a color. Here is an example: Gold, Silver, Silver, Silver, Silver, Bronze, Bronze, Bronze, Gold.
The corresponding picture will be as shown below:

转存失败重新上传取消转存失败重新上传取消转存失败重新上传取消
Figure 1

If some adjacent boxes are all of the same color, and both the box to its left(if it exists) and its right(if it exists) are of some other color, we call it a 'box segment'. There are 4 box segments. That is: gold, silver, bronze, gold. There are 1, 4, 3, 1 box(es) in the segments respectively.

Every time, you can click a box, then the whole segment containing that box DISAPPEARS. If that segment is composed of k boxes, you will get k*k points. for example, if you click on a silver box, the silver segment disappears, you got 4*4=16 points.

Now let's look at the picture below:

转存失败重新上传取消
Figure 2

The first one is OPTIMAL.

Find the highest score you can get, given an initial state of this game.

Input

The first line contains the number of tests t(1<=t<=15). Each case contains two lines. The first line contains an integer n(1<=n<=200), the number of boxes. The second line contains n integers, representing the colors of each box. The integers are in the range 1~n.

Output

For each test case, print the case number and the highest possible score.

Sample Input

   

    

     

      

     
     

      

       2
      
     
    

     

      

     
     

      

       9
      
     
    

     

      

     
     

      

       1 2 2 2 2 3 3 3 1
      
     
    

     

      

     
     

      

       1
      
     
    

     

      

     
     

      

       1
      
     
   

Sample Output

   

    

     

      

     
     

      

       Case 1: 29
      
     
    

     

      

     
     

      

       Case 2: 1
      
     
   

Source

Liu Rujia@POJ

 题意：给你一个颜色块序列，每次你可以选择删除一些相同颜色且相邻的方块，收益是删除方块数目的平方，单个方块也可以删除，收益为1，那么，最大的收益是多少呢

题解：先给出方程dp[l][r][k]，l，r代表区间端点，k代表想要和端点r颜色相同的颜色块的个数

对于给定的方块，我们先做一下处理，把相同的块存到一起，消除的时候一块消除，这样肯定比单个单个的删除获得的收益大，那么，重点！！！这么多的块，怎么才能让程序做出最优的消除方案呢？我们这样想，如果合并以后没有任何一样颜色的方块了，那么是不就算一下每个合并后方块的平方和，也就是这样递归计算：calc(l,r-1,0)+(len[r]+k)*(len[r]+k) ；而如果第l个块和第r个块颜色一样，那我们要把他们一起删除的话，就要把区间[ l+1，r-1 ]的方块全部删除掉，而[ l+1，r-1 ]区间内也可能存在和第r块一样的颜色块，那我们在递归搜索一下是否存在，若存在，计算进来，没有的话，直接返回原值，而搜索的话，我们在递归的时候枚举一下也就是   

   

    

     

      

     
     

      

       for(
       int i=l;i<r;i++)
      
     
    

     

      

     
     

      

           {
      
     
    

     

      

     
     

      

               
       if(box[i]==box[r])
      
     
    

     

      

     
     

      

                   dp[l][r][k] = max( dp[l][r][k] , calc(l,i,len[r]+k)+calc(i+
       1,r
       -1,
       0) );
      
     
    

     

      

     
     

      

           }
      
     
   

有点分治的感觉。把上面的情况组合起来就好了！

  

   

    

     

    
    

     

      #include <cstdlib>
     
    
   

    

     

    
    

     

      #include <cstdio>
     
    
   

    

     

    
    

     

      #include <queue>
     
    
   

    

     

    
    

     

      #include <cmath>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <set>
     
    
   

    

     

    
    

     

      #include <map>
     
    
   

    

     

    
    

     

      #include <string>
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      #define ll long long
     
    
   

    

     

    
    

     

      #define mem(vis,x) memset(vis,x,sizeof(vis))
     
    
   

    

     

    
    

     

      #define TLE std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
     
    
   

    

     

    
    

     

      #define test(n) cout<<"Test "<<n<<endl;
     
    
   

    

     

    
    

     

      #define pb push_back
     
    
   

    

     

    
    

     

      #define rp(n) for(int i=1;i<=n;i++)
     
    
   

    

     

    
    

     

      #define rep(n,m) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
     
    
   

    

     

    
    

     

      const ll mod = 
      1000000007 ;
     
    
   

    

     

    
    

     

      const 
      int INF=
      0x3f3f3f3f;
     
    
   

    

     

    
    

     

      template<
      class T> inline T read(){T x=
      0,w=
      1;
      char c=getchar();
      for(;!
      isdigit(c);c=getchar())
      if(c==
      '-') w=-w;
      for(;
      isdigit(c);c=getchar()) x=x*
      10+c-
      '0';
      return x*w;}
     
    
   

    

     

    
    

     

      template<
      class T> inline T read(T&x){
      return x=read<T>();}
     
    
   

    

     

    
    

     

      using 
      namespace 
      std;
     
    
   

    

     

    
    

     

      const 
      int mxn = 
      1e5+
      7 ;
     
    
   

    

     

    
    

     

      ll n,t,m,k,l,r;
     
    
   

    

     

    
    

     

      /// ll far[mxn] , vis[1600000] , flag[mxn] , dep[mxn] ,dp[mxn][21] , head[mxn] , cnt ,ver[mxn] , lg[mxn] , prime[20202022] ;
     
    
   

    

     

    
    

     

      /// void getlg(){lg[1] = 0 ; for(int i=2;i<=n+1;i++) lg[i] = lg[i/2]+1;}
     
    
   

    

     

    
    

     

      /// struct node{int to , nx ;}node[mxn<<1];
     
    
   

    

     

    
    

     

      int dp[
      210][
      210][
      210],box[mxn],len[mxn] ;
     
    
   

    

     

    
    

     

      int calc(int l,int r,int k)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    
      if(dp[l][r][k]) 
      return dp[l][r][k] ;
     
    
   

    

     

    
    

     
    
      if(l==r) 
      return (len[r]+k)*(len[r]+k);
     
    
   

    

     

    
    

     

          dp[l][r][k] = calc(l,r
      -1,
      0)+(len[r]+k)*(len[r]+k);
     
    
   

    

     

    
    

     
    
      for(
      int i=l;i<r;i++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        
      if(box[i]==box[r])
     
    
   

    

     

    
    

     

                  dp[l][r][k] = max( dp[l][r][k] , calc(l,i,len[r]+k)+calc(i+
      1,r
      -1,
      0) );
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      return dp[l][r][k];
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    
      int Case = 
      0 ;
     
    
   

    

     

    
    

     

          read(t);
     
    
   

    

     

    
    

     
    
      while(t--)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              read(n);Case++;
     
    
   

    

     

    
    

     
        
      int now = 
      -1 , cnt = 
      0;
     
    
   

    

     

    
    

     

              mem(len,
      0); mem(dp,
      0);
     
    
   

    

     

    
    

     

              rp(n)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  read(k) ;
     
    
   

    

     

    
    

     
            
      if(k==now) len[cnt]++;
     
    
   

    

     

    
    

     
            
      else box[++cnt] = k , len[cnt]++ , now = k ;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        
      cout<<
      "Case "<<Case<<
      ": "<<calc(l,cnt,
      0)<<
      endl;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  

石子合并DP题解

E. Array Shrinking

You are given an array a1,a2,…,ana1,a2,…,an. You can perform the following operation any number of times:

• Choose a pair of two neighboring equal elements ai=ai+1ai=ai+1 (if there is at least one such pair).
• Replace them by one element with value ai+1ai+1.

After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array aa you can get?

Input

The first line contains the single integer nn (1≤n≤5001≤n≤500) — the initial length of the array aa.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤10001≤ai≤1000) — the initial array aa.

Output

Print the only integer — the minimum possible length you can get after performing the operation described above any number of times.

Examples

input

Copy

5
4 3 2 2 3

output

Copy

2

input

Copy

7
3 3 4 4 4 3 3

output

Copy

2

input

Copy

3
1 3 5

output

Copy

3

input

Copy

1
1000

output

Copy

1

Note

In the first test, this is one of the optimal sequences of operations: 44 33 22 22 33 →→ 44 33 33 33 →→ 44 44 33 →→ 55 33.

In the second test, this is one of the optimal sequences of operations: 33 33 44 44 44 33 33 →→ 44 44 44 44 33 33 →→ 44 44 44 44 44 →→ 55 44 44 44 →→ 55 55 44 →→ 66 44.

In the third and fourth tests, you can't perform the operation at all.

  

   

    

     

    
    

     

      #include <cstdlib>
     
    
   

    

     

    
    

     

      #include <cstdio>
     
    
   

    

     

    
    

     

      #include <queue>
     
    
   

    

     

    
    

     

      #include <cmath>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <set>
     
    
   

    

     

    
    

     

      #include <map>
     
    
   

    

     

    
    

     

      #include <string>
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      #define ll long long
     
    
   

    

     

    
    

     

      #define mem(vis,x) memset(vis,x,sizeof(vis))
     
    
   

    

     

    
    

     

      #define TLE std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
     
    
   

    

     

    
    

     

      #define test(n) cout<<"Test "<<n<<endl;
     
    
   

    

     

    
    

     

      #define pb push_back
     
    
   

    

     

    
    

     

      #define rp(n) for(int i=1;i<=n;i++)
     
    
   

    

     

    
    

     

      #define rep(n,m) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
     
    
   

    

     

    
    

     

      const ll mod = 
      1000000007 ;
     
    
   

    

     

    
    

     

      const 
      int INF=
      0x3f3f3f3f;
     
    
   

    

     

    
    

     

      ll exgcd(ll a,ll b, ll &x,ll &y){
      if(!b) {x = 
      1 ,y = 
      0 ;
      return a;}ll d = exgcd(b,a%b,y,x);y-=a/b*x;
      return d;}
     
    
   

    

     

    
    

     

      template<
      class T> inline T read(){T x=
      0,w=
      1;
      char c=getchar();
      for(;!
      isdigit(c);c=getchar())
      if(c==
      '-') w=-w;
      for(;
      isdigit(c);c=getchar()) x=x*
      10+c-
      '0';
      return x*w;}
     
    
   

    

     

    
    

     

      template<
      class T> inline T read(T&x){
      return x=read<T>();}
     
    
   

    

     

    
    

     

      using 
      namespace 
      std;
     
    
   

    

     

    
    

     

      const 
      int mxn = 
      1e3+
      7 ;
     
    
   

    

     

    
    

     

      ll n,t,m,k,l,r;
     
    
   

    

     

    
    

     

      /// ll far[mxn] , vis[1600000] , flag[mxn] , dep[mxn] ,dp[mxn][21] , head[mxn] , cnt ,ver[mxn] , lg[mxn] , prime[20202022] ;
     
    
   

    

     

    
    

     

      /// void getlg(){lg[1] = 0 ; for(int i=2;i<=n+1;i++) lg[i] = lg[i/2]+1;}
     
    
   

    

     

    
    

     

      /// struct node{int to , nx ;}node[mxn<<1];
     
    
   

    

     

    
    

     

      int fac[mxn] , dp[mxn][mxn] , a[mxn] ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          read(n);
     
    
   

    

     

    
    

     

          rp(n) read(a[i]),dp[i][i]=a[i],fac[i]=n+
      1;
     
    
   

    

     

    
    

     
    
      for(
      int len = 
      1 ; len <=n ;len++)
      /// 枚举长度
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        
      for(
      int l=
      1;l<=n;l++) 
      /// 以l
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            
      int r = l + len - 
      1 ;   
      /// 区间右端点
     
    
   

    

     

    
    

     
            
      for(
      int k=l;k<r;k++) 
      /// 枚举断点
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     
                
      if( dp[l][k]==dp[k+
      1][r] && dp[l][k] )
     
    
   

    

     

    
    

     

                          dp[l][r] = dp[l][k] + 
      1 ;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      /*
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       for(int j=1;j<=n;j++)
     
    
   

    

     

    
    

     

       cout<<dp[i][j]<<" ";
     
    
   

    

     

    
    

     

       cout<<endl;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     
    
      for(
      int r=
      1;r<=n;r++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        
      if(dp[
      1][r]) {fac[r] = 
      1 ; 
      continue;}
     
    
   

    

     

    
    

     
        
      for(
      int l=
      2;l<=r;l++)
     
    
   

    

     

    
    

     
            
      if(dp[l][r])
     
    
   

    

     

    
    

     

                      fac[r] = min(fac[r],fac[l
      -1]+
      1);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      cout<<fac[n]<<
      endl;
     
    
   

    

     

    
    

     

      }