【JSOI 2007】祖玛

【题目链接】

           点击打开链接

【算法】

           f[i][j]表示第i段到第j段，最少需要多少次全部消除

          那么，当color[i] = color[j]时 ：

                  若s[i] + s[j] > 2,根据题目中所说的“连锁反应”，很容易得到f[i][j] = f[i+1][j-1]

                  若s[i] + s[j] = 2，我们就需要先消除i到j，然后再花一颗珠子消除剩余的,则 f[i][j] = f[i+1][j-1] + 1

         否则，显然有 : f[i][j] = max{f[i][k] + f[k+1][j]} (i <= k < j)

【代码】

  

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1020
const int INF = 1e9;

struct info 
{
    int s,col;
} t[MAXN];

int i,j,x,len,n,k;
int a[MAXN],f[MAXN][MAXN];

template <typename T> inline void read(T &x)
{
    int f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;    
}
template <typename T> inline void write(T x)
{
    if (x < 0) 
    {
        putchar('-');
        x = -x;    
    }    
    if (x > 9) write(x/10);
    putchar(x%10+'0');
}
template <typename T> inline void writeln(T x)
{
    write(x);
    puts("");
}

int main()
{
    
    read(n);
    for (i = 1; i <= n; i++) read(a[i]);
    len = 1;
    t[1].col = a[1];
    t[1].s = 1;
    for (i = 2; i <= n; i++)
    {
        if (a[i] == a[i-1]) t[len].s++;
        else
        {
            len++;
            t[len].s = 1;
            t[len].col = a[i];    
        }     
    }
    for (i = 1; i <= len; i++)
    {
        for (j = 1; j <= len; j++)
        {
            f[i][j] = INF;
        }
    }
    for (i = 1; i <= len; i++)
    {
        if (t[i].s == 1) f[i][i] = 2;
        else f[i][i] = 1;
    }
    for (k = 2; k <= len; k++)
    {
        for (i = 1; i <= len - k + 1; i++)
        {
            j = i + k - 1;
            if (t[i].col == t[j].col)
            {
                if (t[i].s + t[j].s > 2) f[i][j] = f[i+1][j-1];
                else f[i][j] = f[i+1][j-1] + 1;
            }
            for (x = i; x < j; x++) f[i][j] = min(f[i][j],f[i][x]+f[x+1][j]);
        }
    }
    writeln(f[1][len]);
    
    return 0;
}