poj 1390 Blocks - dblank

poj 1390 Blocks

传送门:Blocks

题意:N个方盒(box)摆成一排,每个方盒有自己的颜色。连续摆放的同颜色方盒构成一个方盒片段(box segment)。下图中共有四个方盒片段,每个方盒片段分别有1、4、3、1个方盒玩家每次点击一个方盒,则该方盒所在方盒玩家每次点击一个方盒,则该方盒所在方盒片段就会消失。若消失的方盒片段中共有k个方盒,则玩家获得k*k个积分。问最大能够获得积分。

思路:定义dpi[len]为消除了i~j并且右边存在长度为len和j块的颜色相同的最大获得积分,然后对于每一个[i, j],我们考虑消除j块的情况,j块可以和len一起消除,还可以在[i,j-1]找到一块和它一样的然后把他们中间的一起消除,然后消除这一大块,我们在这几个状态里面选取一个最大获得积分的状态进行转移。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 200 + 10, Mod = 1000000000;
typedef long long ll;
int dpN[N], n, k;
struct node
{
    int c, l;
} p[N];
int solve(int i, int j, int len)
{
    if(dpi[len]!=-1)
        return dpi[len];
    int res = (p[j].l + len)*(p[j].l + len);//和右边的同色块进行消除
    if(i == j)
        return res;
    res += solve(i, j-1, 0);
    for(int k = i; k<=j-1; k++)
    {
        if(p[k].c != p[j].c)
            continue;
        int sum = solve(k+1, j-1, 0);//把k和j之间的块消除的最大获得积分
        sum += solve(i, k, len + p[j].l);//消除[i, k]区间,也就是k块和j块一起消除
        res = max(res, sum);//取最大状态进行转移
    }
    return dpi[len] = res;
}
int main()
{
    int t, x;
    cin>>t;
    for(int cas = 1; cas<=t; cas++)
    {
        int lastc = 0;
        k = 0;
        memset(dp, -1, sizeof(dp));
        scanf("%d", &n);
        for(int i = 1; i<=n; i++)
        {
            scanf("%d", &x);
            if(x == lastc)
                p[k].l++;
            else
            {
                k++;
                p[k].c = x;
                p[k].l = 1;
                lastc = x;
            }
        }
        iterator
        printf("Case %d: %dn",cas, solve(1, k, 0));
    }
    return 0;
}

 

相关文章

发表新评论