UVA 10559 Blocks(区间DP&&递推)

题目大意：给你玩一个一维版的消灭星星，得分是当前消去的区间的长度的平方，求最大得分。

现在分析一下题目

因为得分是长度的平方，不能直接累加，所以在计算得分时需要考虑前一个状态所消去的长度，仅用dp[l][r]来表示区间最大得分是不足以用来转移的。

我们的解决方法是：增加一维预测未来可能会出现的情况，用dp[l][r][t]表示区间[l,r]之后附加t个与r同色的方块时所能得到的最大值。为了降低时间复杂度，我们可以在读入时处理一下，将一段长度为a、颜色为b的区间k表示成一个len[k]=a,col[k]=b的“点”。这样，当我们计算dp[l][r][0]时，首先尝试直接消除区间r，得到dp[l][r][0]=dp[l][r-1][0]+(len[r])^2，接着，将它之后所有可能的附加t个同色方块的情况都算出来：dp[l][r][t]=dp[l][r-1][0]+(len[r]+t)^2。之后，在[l,r-1]之间寻找可能与区间r同色的区间k，若col[r]==col[k]，则尝试消除区间r与k之间的所有方块，让区间r与k并在一起计算分数并更新所有dp[l][r][t]的值：dp[l][r][t]=max(dp[l][r][t],dp[l][k][len[r]+t]+dp[k+1][r-1][0])。最后dp[1][n][0]即为答案。（n为一开始同色区间的数量）

代码：（140ms,用递推速度就是不一样，比记搜不知道高到哪里去了）

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int col[],len[],dp[][][];

int sum[];

//by sclbgw7

inline int sq(int x)

{return x*x;}

inline int maxn(int x,int y)

{return x>y?x:y;}

int main()

{

    int T,time;

    scanf("%d",&T);

    for(time=;time<=T;++time)

    {

        int n=,m,t1;//m为方块个数，n为区间个数

        scanf("%d",&m);

        for(int i=;i<=m;++i)

        {

            scanf("%d",&t1);

            if(t1==col[n])

              ++len[n];

            else

            {

                col[++n]=t1;

                len[n]=;

            }

        }

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

          sum[i]=sum[i-]+len[i];//sum为前缀和，用于限定预测t的范围

        memset(dp,,sizeof(dp));

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

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

            {

                int r=l+i,re=sum[n]-sum[r];//re为当前t可能用到的最大值

                for(int t=;t<=re;++t)

                  dp[l][r][t]=dp[l][r-][]+sq(t+len[r]);

                for(int k=r-;k>=l;--k)

                  if(col[k]==col[r])

                    for(int t=;t<=re;++t)

                      dp[l][r][t]=maxn(dp[l][r][t],dp[l][k][len[r]+t]+dp[k+][r-][]);

            }

        printf("Case %d: %d\n",time,dp[][n][]);

        //神坑！！！！！冒号之后要加一个空格！！！！！！！

    }

    return ;

}

巴特西

UVA 10559 Blocks(区间DP&&递推)

最新文章

热门文章