题解
第一道自己码出的区间DP快庆祝一哈
2048
每次可以合并任意相邻的两个数字，得到的不是翻倍而是+1
dp[L][R] 区间 L~R 合并结果
然后拆成左区间和右区间，看看他们能不能合并，更新ans
注意如果最后枚举到的总区间 1~n ，那么就要考虑取左右区间最大值了，因为可能左右区间不能合并，那么左右区间最大值就是最终答案
代码
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<queue> using namespace std; inline int read() { int ans=0; char last=‘ ‘,ch=getchar(); while(ch<‘0‘||ch>‘9‘) last=ch,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) ans=ans*10+ch-‘0‘,ch=getchar(); if(last==‘-‘) ans=-ans; return ans; } int n,a[300]; int dp[300][300]; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(),dp[i][i]=a[i]; for(int l=2;l<=n;l++) for(int i=1;i+l-1<=n;i++) { int j=i+l-1; for(int k=i;k<j;k++) { dp[i][j]=max(dp[i][j],(dp[i][k]+1)*(dp[i][k]==dp[k+1][j])); if(l==n) dp[i][j]=max(dp[i][j],max(dp[i][k],dp[k+1][j])); } } printf("%d\n",dp[1][n]); return 0; }
原文：https://www.cnblogs.com/xiaoyezi-wink/p/11487279.html