【DP】【2017.7.7普及】和谐数
2024-07-06题目描述
给定一个长度为
N
N
N的序列
a
a
a，对于每一个数都可选或不选，把选出的数有序组成一个新的序列
b
b
b，使
b
b
b序列的“和谐数”最大。 一个序列的和谐数如下定义：对于位置
i
i
i，如果第奇数次选的则加上
b
i
b_i
bi，偶数次选的则减去
b
i
b_i
bi 注意：新的序列
b
b
b必须是从左到右依次在
a
a
a序列选择的，即不能打乱顺序。 输入 输入的第一行是一个
n
n
n，第二行为
n
n
n个数，即序列
a
a
a 输出 输出一行一个整数，即表示最大的和谐数 样例输入
5 1 2 3 4 5
Sample Input2 6 1 3 5 4 6 8
样例输出
5
Sample Output2 9
数据范围限制 对于20%的数据，
1
<
=
n
<
=
20
1<=n<=20
1<=n<=20 对于50%的数据，
1
<
=
n
<
=
1000
1<=n<=1000
1<=n<=1000 对于100%的数据，
1
<
=
n
<
=
10000000
,
1
<
=
A
i
<
=
100
1<=n<=10000000,1<=Ai<=100
1<=n<=10000000,1<=Ai<=100
思路
考试的时候冥思苦想，就是T。。（说脏话好像要罚钱来着） D算不出来第一个样例。后来gjy巨佬告诉我只选最后一个。。。c
设
f
[
i
]
[
0
]
f[i][0]
f[i][0]为第
i
i
i个数偶数的时候选的最优解
f
[
i
]
[
1
]
f[i][1]
f[i][1]为第
i
i
i个数奇数的时候选的最优解
f
[
i
]
[
1
]
=
m
a
x
(
f
[
i
−
1
]
[
1
]
,
f
[
i
−
1
]
[
0
]
+
a
[
i
]
)
f[i][1]=max(f[i-1][1],f[i-1][0]+a[i])
f[i][1]=max(f[i−1][1],f[i−1][0]+a[i])
f
[
i
]
[
0
]
=
m
a
x
(
f
[
i
−
1
]
[
1
]
−
a
[
i
]
,
f
[
i
−
1
]
[
0
]
)
f[i][0]=max(f[i-1][1]-a[i],f[i-1][0])
f[i][0]=max(f[i−1][1]−a[i],f[i−1][0])
这么简单 （心虚） 的转移方程自己列一列板栗就可以了
因为
f
[
i
]
f[i]
f[i]只跟
f
[
i
−
1
]
f[i-1]
f[i−1]有关，所以我们可以用滚动数组。但是。。。我不会，所以我用了一种简单粗暴的方法
#include
#include
using namespace std;
long long f1,f0,x1,x0,n;
int main(){
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
x1=max(f1,f0+a);
x0=max(f1-a,f0);
f1=x1,f0=x0;
}
printf("%lld",max(f1,f0));
}