给定一个1*n的地图，在里面玩2048，每次可以合并相邻两个（数值范围1-40），问最大能合出多少。注意合并后的数值并非加倍而是+1，例如2与2合并后的数值为3。‘
区间dp
被一个点wa了半天
见代码
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e4+5; int a[N],n,dp[N][N]; int main() { int ans=0; RI(n); rep(i,1,n)RI(a[i]),dp[i][i]=a[i],ans=max(ans,a[i]); repp(i,n-1,1) rep(j,i+1,n) rep(k,i,j-1) { if(dp[i][k]==dp[k+1][j])dp[i][j]=max(dp[i][j],dp[i][k]+1); //else dp[i][j]=max(dp[i][j],max(dp[i][k],dp[k+1][j]));//加上这条肯定错的！！！ ans=max(ans,dp[i][j]); } cout<<ans; return 0; }