[洛谷] P3146 [USACO16OPEN]248 G (区间DP)
题目描述
Bessie likes downloading games to play on her cell phone, even though she doesfind the small touch screen rather cumbersome to use with her large hooves.
She is particularly intrigued by the current game she is playing.The game starts with a sequence of NN positive integers (2 leq Nleq 2482≤N≤248), each in the range 1 ldots 401…40. In one move, Bessie cantake two adjacent numbers with equal values and replace them a singlenumber of value one greater (e.g., she might replace two adjacent 7swith an 8). The goal is to maximize the value of the largest numberpresent in the sequence at the end of the game. Please help Bessiescore as highly as possible!
给定一个1*n(2<=N<=248)的地图，在里面玩2048，每次可以合并相邻两个（数值范围1-40），问最大能合出多少。注意合并后的数值并非加倍而是+1，例如2与2合并后的数值为3。
思路：
首先数据范围比较小，
$ dp[l][r][s] $ 为 $l-r$ 区间能否组合成为$s$
我就打了个记忆化搜索+一些小剪枝看看能不能爆过去，预计时间复杂度$O(n^4)$（随便口胡的一个复杂度，可能假了）,常数也不咋地，代码如下：
1 #include <bits/stdc++.h> 2 3 #define rep(i,x,y) for(int i=(x);i<=(y);++i) 4 #define _max(a,b) (a)>(b)? (a):(b) 5 #define _min(a,b) (a)<(b)? (a):(b) 6 7 using namespace std; 8 typedef long long ll; 9 typedef pair<int,int> pii; 10 typedef pair<ll,int> pli; 11 typedef pair<int,ll> pil; 12 typedef pair<ll,ll> pll; 13 const int MAXN=250; 14 int dp[MAXN][MAXN][50]; 15 int n; 16 int a[MAXN]; 17 18 int solve(int l,int r,int k){ 19 if(dp[l][r][k]) return dp[l][r][k]; 20 if(l==r) return dp[l][r][k]; 21 rep(i,l,r-1){ 22 if(!dp[l][i][k-1]) dp[l][i][k-1]=solve(l,i,k-1); 23 if(!dp[i+1][r][k-1]) dp[i+1][r][k-1]=solve(i+1,r,k-1); 24 if(dp[l][i][k-1]!=-1&&dp[i+1][r][k-1]!=-1) return dp[l][r][k]=1; 25 } 26 27 return dp[l][r][k]=-1; 28 } 29 30 void init(int u){ 31 rep(i,0,49) dp[u][u][i]=-1; 32 } 33 34 int main(){ 35 cin>>n; 36 int mx=0,mi=99; 37 rep(i,1,n) scanf("%d",a+i),init(i),dp[i][i][a[i]]=1,mx=max(mx,a[i]); 38 int ans=0; 39 rep(i,1,n){ 40 rep(j,i,n){ 41 mx=0,mi=99; 42 rep(k,i,j) mx=max(mx,a[k]),mi=min(mi,a[k]); 43 rep(k,mi,mx+9){ 44 dp[i][j][k]=solve(i,j,k); 45 if(dp[i][j][k]==1) ans=max(ans,k); 46 } 47 } 48 } 49 cout<<ans<<endl; 50 return 0; 51 }
不开O2，T了好几个点, 41pts，开了O2之后勉强卡过去：
然后翻了一下题解区，看了一下别人写的思路,先枚举区间$l-r$的大小，再枚举起点和划分成分两块的地方，最后枚举能组合成的大小,时间复杂度就是妥妥的$O(n^4)$，代码如下：
1 #include <bits/stdc++.h> 2 3 #define rep(i,x,y) for(int i=(x);i<=(y);++i) 4 #define _max(a,b) (a)>(b)? (a):(b) 5 #define _min(a,b) (a)<(b)? (a):(b) 6 7 using namespace std; 8 typedef long long ll; 9 typedef pair<int,int> pii; 10 typedef pair<ll,int> pli; 11 typedef pair<int,ll> pil; 12 typedef pair<ll,ll> pll; 13 const int MAXN=250; 14 int dp[MAXN][MAXN][50]; 15 int n; 16 int a[MAXN]; 17 18 void init(int u){ 19 rep(i,0,49) dp[u][u][i]=-1; 20 } 21 22 int main(){ 23 cin>>n; 24 int mx=0,mi=99; 25 rep(i,1,n) scanf("%d",a+i),init(i),dp[i][i][a[i]]=1,mx=max(mx,a[i]); 26 int ans=0; 27 rep(k,1,n-1){ 28 for(int i=1;i+k<=n;++i){ 29 int l=i,r=i+k; 30 mx=0,mi=99; 31 rep(s,l,r) mx=max(mx,a[s]),mi=min(mi,a[s]); 32 for(int j=l;j<r;++j){ 33 rep(s,mi,mx+9){ 34 if(dp[l][j][s-1]==1&&dp[j+1][r][s-1]==1) dp[l][r][s]=1; 35 if(dp[l][r][s]==1) ans=max(ans,s); 36 } 37 } 38 } 39 } 40 cout<<ans<<endl; 41 return 0; 42 }
不开O2也能过去：
开了O2之后：
暴力归暴力，标算还是得学的
$dp[l][r]$ 代表$l-r$区间能完全合并的最大数值，状态转移就是
$if(dp[i][pos] == dp[pos+1][j])$
$dp[i][j]=max(dp[i][j],dp[i][pos]+1)$
枚举时先枚举区间大小，再枚举起点，再枚举划分点，复杂度$O(n^3)$:
1 #include <bits/stdc++.h> 2 3 #define rep(i,x,y) for(int i=(x);i<=(y);++i) 4 #define _max(a,b) (a)>(b)? (a):(b) 5 #define _min(a,b) (a)<(b)? (a):(b) 6 7 using namespace std; 8 typedef long long ll; 9 typedef pair<int,int> pii; 10 typedef pair<ll,int> pli; 11 typedef pair<int,ll> pil; 12 typedef pair<ll,ll> pll; 13 14 const int MAXN=260; 15 16 int dp[MAXN][MAXN]; 17 int n; 18 int a[MAXN]; 19 20 int main(){ 21 cin>>n; 22 rep(i,1,n) scanf("%d",a+i),dp[i][i]=a[i]; 23 int ans=0; 24 rep(k,2,n){ 25 rep(i,1,n-k+1){ 26 int j=i+k-1; 27 for(int pos=i;pos<j;++pos){ 28 if(dp[i][pos]==dp[pos+1][j]){ 29 dp[i][j]=max(dp[i][j],dp[i][pos]+1); 30 ans=max(ans,dp[i][pos]+1); 31 } 32 } 33 } 34 } 35 cout<<ans; 36 return 0; 37 }