Luogu P1651 塔

题目链接


突然发现,我还是太菜了。 这道题做了一个半小时,开始的一个小时想的都是错的,后来还是看了题解,本来我想的是用bool数组$f[i][j]$来表示从木块中选i个木块能否组成j的高度,用0和1表示。后来打了70分(数据好水)才发现这有后效性。

正解

因为题目中讲能否选择几个木块构成两个高度相同的塔,要求输出这个塔的最大高度,那么就可以想到,使用$f[i][j]$来表示选到第i个时,且两个塔的高度差为j时,较高的那个塔的高度,这样便有四个状态可以转移。 - 不放第i个:$f[i][j]=f[i-1][j]$ - 把第i个放到较矮的塔上,矮塔还是矮塔:$f[i][j]=max(f[i][j],f[i-1][j+a[i]])$ - 放到较高的塔上,高塔当然高:$f[i][j]=max(f[i][j],f[i-1][j-a[i]]+a[i])$ - 放到较低的塔上,低塔变成高塔:$f[i][j]=max(f[i][j],f[i-1][a[i]-j]+j)$ 综上,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;

int n,a[55],sum;
int f[55][500005];

int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=sum;j>=0;j--){
f[i][j]=max(f[i][j],f[i-1][j]);
f[i][j]=max(f[i][j],f[i-1][j+a[i]]);
if(j>=a[i]) f[i][j]=max(f[i][j],f[i-1][j-a[i]]+a[i]);
if(j<=a[i]) f[i][j]=max(f[i][j],f[i-1][a[i]-j]+j);
}
}
if(f[n][0]<=0) cout<<"-1";
else cout<<f[n][0];
return 0;
}
# dp

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×