首页 > 代码库 > BZOJ 4580: [Usaco2016 Open]248

BZOJ 4580: [Usaco2016 Open]248

Description

一个序列,每次可以把相邻的两个数合为一个,价值+1,求最后的最大价值.

Sol

区间DP.

\(f[i][j]\) 表示 \(i-j\) 中合成一个数字为多少,转移就是枚举断点,断点两边的价值一样,就合并.

复杂度 \(O(n^3)\)

Code

/**************************************************************    Problem: 4580    User: BeiYu    Language: C++    Result: Accepted    Time:308 ms    Memory:1544 kb****************************************************************/ #include <cstdio>#include <cstring>#include <iostream>using namespace std; const int N = 255;const int M = 50;  int n,ans;int a[N];int f[N][N]; inline int in(int x=0){ scanf("%d",&x);return x; }int DFS(int l,int r){    if(l == r) return f[l][r]=a[l];    if(~f[l][r]) return f[l][r];    f[l][r]=0;    for(int i=l;i<r;i++){        int x=DFS(l,i),y=DFS(i+1,r);        if(x!=0 && y!=0 && x == y) f[l][r]=max(f[l][r],x+1);    }ans=max(ans,f[l][r]);return f[l][r];}int main(){    n=in();    for(int i=1;i<=n;i++) a[i]=in(),ans=max(ans,a[i]);         memset(f,0xff,sizeof(f));         for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) DFS(i,j);     //  for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) cout<<i<<" "<<j<<" "<<DFS(i,j)<<endl;         cout<<ans<<endl;    return 0;}

  

BZOJ 4580: [Usaco2016 Open]248