问题标题: 酷町堂：4243 真不是只改个符号那么简单啊

Question

0

已解决

黄子扬

初级天翼

#include<bits/stdc++.h>
using namespace std;
int a[25],n,dp[25],ans=-233333333;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	    scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	    dp[i]=max(dp[i-1]*a[i],a[i]);
	for(int i=1;i<=n;i++)
	    ans=max(ans,dp[i]);
	cout<<ans<<endl;
	return 0;
}

WA20分了，是什么没有考虑到吗，求大家hack/kel

黄子扬在2020-08-02 09:27:37追加了内容

#include<bits/stdc++.h>
using namespace std;
int a[25],n,dp[25],ans=-233333333;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	    scanf("%d",&a[i]);
	dp[1]=a[1];
	for(int i=2;i<=n;i++)
	    dp[i]=max(dp[i-1]*a[i],a[i]);
	for(int i=1;i<=n;i++)
	    ans=max(ans,dp[i]);
	cout<<ans<<endl;
	return 0;
}

修改后过了

5
-1 -1 -1 -1 -1

的样例，但是依旧WA20分

黄子扬在2020-08-02 09:30:36追加了内容

自己又找到一个hack数据

5
-1 -2 -3 -4 0

因为乘法会变号，所以如果乘后可能变成符号是不考虑f[i-2]能带来的影响的？

准备从dp[i-1]*a[i],dp[i-2]*dp[i-1]*a[i],a[i]三者中取max了

黄子扬在2020-08-02 09:32:35追加了内容

得了，改完更错了，我dp真渣

Answer 1

已采纳

王子健

初级天翼

//5
//-1 -1 -1 -1 -1

这个样例你可以试一下

王子健在2020-08-02 09:22:32追加了内容

你的dp[i-1]在第一个的时候会与-1相乘，你看看它是不是都变成0了？0>-1啊

Answer 2

董子墨

中级天翼

我WA50，代码仅供参考

#include<iostream>
using namespace std;
long long f[25],ans;
int a[25],n;
int main(){
    cin>>n;
    f[0]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i]=f[i-1]*a[i];
    }
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++){
            if(f[i-1]!=0)
                ans=max(ans,f[j]/f[i-1]);
        }
    cout<<ans;
    return 0;
}

Answer 3

董子墨

中级天翼

你要定义2个状态数组

因为：

如果前i-1个数，连续子序列的最大值是-1，最小值是-8 ，且当前a[i]是-1

那么：最大值：(-1)*(-1)=1;

最小值：(-8)*(-1)=8;

所以状态转移方程有4个，具体自己想

问题标题: 酷町堂：4243 真不是只改个符号那么简单啊

3 个回答: