[USACO16OPEN]248

题目描述

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

Solution

入门区间DP

f[i][j]表示[i,j]能合并出的最大的数

转移的顺序第一次写错了。。。

#include
     
      using namespace std;const int MAXN = 300;typedef long long ll;inline ll read(){    ll f=1,x=0;    char ch;    do    {        ch=getchar();        if(ch=='-') f=-1;    }while(ch<'0'||ch>'9');    do    {        x=(x<<3)+(x<<1)+ch-'0';        ch=getchar();    }while(ch>='0'&&ch<='9');    return f*x;}int n;int a[MAXN]; int f[MAXN][MAXN],ans;int main(){    n=read();    for(int i=1;i<=n;i++) a[i]=read(),f[i][i]=a[i];    for(int i=n-1;i>=1;i--)        for(int j=i+1;j<=n;j++)            for(int k=i;k