柚子快报邀请码778899分享：算法 动态规划学习（2）
洛谷 P3147 262144 P
题干很简单，有
n
n
n 个正整数
a
i
(
1
≤
a
i
≤
40
)
a_i(1\leq a_i\leq 40)
ai(1≤ai≤40) 排成一排，任意两个相邻且相等的数可以合成一个比它们大
1
1
1 的新数，要我们求出能够合成出的最大的数。 输入：第一行
n
n
n 以及随后这
n
n
n 个数
a
i
(
i
=
1
,
2
,
⋯
,
n
)
a_i(i=1,2,\cdots,n)
ai(i=1,2,⋯,n)。 输出：能够合成的最大的数。
题目分析
我们考虑一个这样的
d
p
dp
dp 数组，
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示从
a
i
a_i
ai 到
a
j
a_j
aj 这总共
j
−
i
+
1
j-i+1
j−i+1 个数能够合成出来的数值。这些数可能无法合成出一个数，我们设此时
d
p
[
i
]
[
j
]
=
0
dp[i][j]=0
dp[i][j]=0；若能够合成出一个数，那么这个值必定是唯一的。当
d
p
[
i
]
[
k
]
=
d
p
[
k
]
[
j
]
≠
0
dp[i][k]=dp[k][j]\neq 0
dp[i][k]=dp[k][j]=0 时，下列状态转移方程成立：
d
p
[
i
]
[
j
]
=
max
k
{
d
p
[
i
]
[
k
]
+
1
}
(1)
dp[i][j]=\max\limits_k\{dp[i][k]+1\}\tag{1}
dp[i][j]=kmax{dp[i][k]+1}(1)
因此，我们不难在
O
(
n
3
)
O(n^3)
O(n3) 的时间复杂度内解决此题。据此，附上一段代码：
# include
using namespace std;
int n,a[255],ans,dp[255][255];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
ans=max(ans,dp[i][i]=a[i]);
}
for(int len=2;len<=n;len++)
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
for(int mid=l;mid if(dp[l][mid] && dp[l][mid]==dp[mid+1][r]){ dp[l][r]=max(dp[l][r],dp[l][mid]+1); ans=max(ans,dp[l][r]); } } return cout< } 显然这种方法行不通，因为题干给出 2 ≤ n ≤ 262144 2\leq n\leq262144 2≤n≤262144， d p dp dp 数组的空间复杂度炸了， O ( n 3 ) O(n^3) O(n3) 的时间复杂度也炸了。实际上，P3146 248 G 与此题拥有相同的题干，上面的代码能够 AC 题 P3146。 那这个题怎么办？我们可以换一种 d p dp dp 的思路。我们设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示从 a i a_i ai 开始，能够合成到数 j j j 所需要的下标数。也就是说，如果 a i a_i ai 到 a k a_k ak 能够合成出数 j j j 来，则 d p [ i ] [ j ] = k dp[i][j]=k dp[i][j]=k。如果不存在这样的 k k k，我们可以给 d p [ i ] [ j ] dp[i][j] dp[i][j] 赋一个相当大的数。 这直接解决了空间复杂度的问题。注意到 262144 = 2 18 262144=2^{18} 262144=218，假设这 262144 262144 262144 个数全部取到 40 40 40，最终也只能合成到 58 58 58，即 d p dp dp 数组的第二维只需要开到 58 58 58 ，而不是 n n n。 状态转移方程也很容易写出来： d p [ i ] [ j ] = d p [ d p [ i ] [ j − 1 ] + 1 ] [ j − 1 ] (2) dp[i][j]=dp[dp[i][j-1]+1][j-1]\tag{2} dp[i][j]=dp[dp[i][j−1]+1][j−1](2) 嵌套式的状转方程初看很麻烦，实际上能够根据上面的定义仔细理解出来。这样，该题的代码就缩小到了 O ( m n ) O(mn) O(mn)，其中 m ≤ 58 m\leq 58 m≤58。 AC 代码 # include # define NN 262300 # define N 262200 # define M 60 using namespace std; int n,a[N],ans,dp[N][M]; int main(){ cin>>n; for(int j=1;j<=M;j++) dp[n+1][j]=NN; for(int i=1;i<=n;i++){ cin>>a[i]; dp[i][a[i]]=i; ans=max(ans,a[i]); } for(int i=n;i>0;i--){ for(int j=1;j dp[i][j]=NN; for(int j=a[i]+1;j<=M;j++){ if(dp[i][j-1]==NN) dp[i][j]=NN; else{ dp[i][j]=dp[dp[i][j-1]+1][j-1]; if(dp[i][j]-NN) ans=max(ans,j); } } } return cout< } 最后 这两道题再次让我感受到了 dp 的魅力。这两道题的 dp 思想，第一个仔细思考还能想到，第二个就有点开创性了、难以想到了。同一道题，可以有不同的 dp 思路，不同思路的时间复杂度、空间复杂度不尽相同。对于此题，只要稍微修改一下规则，比如 a i a_i ai 与 a j a_j aj 合并后得到 a i + a j a_i+a_j ai+aj，那么 M M M 就会变成一个非常大的数字， O ( m n ) O(mn) O(mn) 的复杂度将劣于 O ( n 3 ) O(n^3) O(n3)。 柚子快报邀请码778899分享：算法 动态规划学习（2） 好文推荐
发表评论