题目链接:http://codeforces.com/problemset/problem/1038/D

题意:

给出 $n$ 个史莱姆,每个史莱姆有一个价值 $a[i]$,一个史莱姆可以吃掉相邻的史莱姆,此时其自身的价值就要减掉被吃掉的那个史莱姆的价值。

史莱姆会不断的互相吞噬直到最后只剩一个,要求你该史莱姆可能的最大价值。

题解:

相当于你在 $n$ 个数前面添加 $+$ 或者 $-$,然后拼成一个算式计算答案。

首先考虑到的是,史莱姆的价值是全正或者全负的情况,这样的话,不可能使得所有价值前都添上 $+$ 或者都添上 $-$,这个特判处理一下就好。

其次,就是有正有负的情况:

  首先,若仅有一个史莱姆身怀正价值,所以在它前面添上 $+$,其余所有史莱姆前面都添上 $-$,此时价值最大化;显然这是可行的,只要“正史莱姆”不停地吃掉相邻的所有“负史莱姆”即可。

  其次,若此时有两个“正史莱姆”,其余全是“负史莱姆”,那么通过一系列吞噬必然能够变成如下两种情况之一:

    “负史莱姆,正史莱姆,正史莱姆”:这种情况,要让两个正史莱姆的价值前面都是 $+$ 号,负史莱姆前面是个 $-$ 号,只需要让 $1$ 吃掉 $2$,再让 $3$ 吃掉 $1$ 即可。

    “正史莱姆,负史莱姆,正史莱姆”:这种情况,只需要让 $2$ 吃掉 $3$,再让 $1$ 吃掉 $2$ 即可。

  这样一来,两个正史莱姆的情况就能转化到一个正史莱姆的情况,以此类推,不难发现,三个正史莱姆可以转化到两个正史莱姆,……,$n$ 个正史莱姆可以转化到 $n-1$ 个正史莱姆。

所以,对于有正有负的情况,可以在所有正史莱姆前添 $+$ 号,所有负史莱姆前添 $-$ 号,即把所有史莱姆的价值的绝对值相加。因为不管怎么样,总有一个对应的吃法可以做到这样。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n;
ll a[maxn];
int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n;
ll mx=-INF, mn=INF, sum=;
for(int i=;i<=n;i++)
cin>>a[i], sum+=abs(a[i]), mx=max(mx,a[i]), mn=min(mn,a[i]); if(n==) {cout<<a[]<<endl;return ;} if(mx<) //全负
cout<<sum+*mx<<endl;
else if(mn>) //全正
cout<<sum-*mn<<endl;
else
cout<<sum<<endl;
}

题解2:

当然,我们也可以不特判全正全负的情况,因为我们现在已经知道了,只要你确保既添加了 $+$ 号也添加了 $-$ 号,不管添加的正负号序列是怎么样的,都是通过某种吞吃方法来做到的。

所以我们可以用 $dp[i][x=0,1][y=0,1]$ 来表示,前 $i$ 个的最大值,$x$ 记录是否已经添加过 $+$ 号,$y$ 记录是否已经添加过 $-$ 号。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n;
ll a[maxn],dp[maxn][][];
int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n;
for(int i=;i<=n;i++) cin>>a[i]; if(n==) {cout<<a[]<<endl;return ;} dp[][][]=a[], dp[][][]=-a[];
dp[][][]=dp[][][]=-INF;
for(int i=;i<=n;i++)
{
dp[i][][]=dp[i-][][]+a[i];
dp[i][][]=dp[i-][][]-a[i]; dp[i][][]=-INF;
dp[i][][]=max(dp[i][][],dp[i-][][]+a[i]);
dp[i][][]=max(dp[i][][],dp[i-][][]-a[i]);
dp[i][][]=max(dp[i][][],dp[i-][][]+abs(a[i]));
} cout<<dp[n][][]<<endl;
}
04-21 03:01