[USACO16OPEN]248

标签：动态规划 区间DP

---

题目描述

给定一个1*n的地图，在里面玩2048，每次可以合并相邻两个（数值范围1-40），问最大能合出多少。注意合并后的数值并非加倍而是+1，例如2与2合并后的数值为3。

输入输出格式

输入格式

The first line of input contains N, and the next N lines give the sequence
of N numbers at the start of the game.

输出格式

Please output the largest integer Bessie can generate.

样例

输入样例#1：
4
1
1
1
2

输出样例#1：
3

题解

首先两个数字相同才能合成，所以如果想让两段数字合并的话，比如首先满足每段数字能合成一个数字，并且这两段合成的数字相同。
因此，这就引出了区间DP的思想了。
设f[i][j]表示区间[i,j]合成一个数字的值，若无法合成便等于-1。所以我们初始化所有f[i][j]值为-1.
则转移方程：
$$f[i][j] = max(f[i][j], f[i][k] + 1(f[i][k] == f[k + 1][j]))$$
$$ans=max(ans,f[i][j])$$
注意我们不能把f[i][j]不合法标志设为0，否则当f[i][k]==0并且f[k][j]==0，那么此时他们两个可以合成为1，但其实这是不合法的。
这里可以设置一组HACK数据，大家可以尝试一下：
12
1 2 1 2 1 2 1 2 1 2 1 2

代码

#include<bits/stdc++.h>
#define N 510
using namespace std;

int n, x, ans = -1;
int f[N][N];

int main()
{
    scanf("%d", &n);
    memset(f, -1, sizeof(f));
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &f[i][i]);
        ans = max(ans, f[i][i]);
    }
    for(int len = 1; len <= n; len ++)
        for(int i = 1; i <= n - len + 1; i ++)
        {
            int j = i + len - 1;
            for(int k = i; k < j; k ++)
                if(f[i][k] == f[k + 1][j] && f[i][k] != -1)
                   f[i][j] = max(f[i][j], f[i][k] + 1);
            ans = max(ans, f[i][j]); 
        }
    printf("%d", ans); 
    return 0;
}