Description 小明对1这个数字情有独钟，当他看到一组数字的时候，首先注意到的是这组数字里面 有多少个1 为了表现他对1的特殊感情,他对一段长度为k的数列定义了其“受喜爱程度”,具体为: 若这一段数列总共有t个数是1，那么这段数列"受喜爱程度"便为m*t-k，其中m是他随 心情给出的个整数。 现在给你一个长度为n的数列，小明想请你求出其非空连续子序列“受喜爱程度"的最大 值。请注意，元素在数列中的顺序不可随意改变。 Input 一行两个整数n和m，其含义同题目描述。 接下来一行有n个以空恪分隔开的整数，第i个数表示该数列内的数ai。 Output 一行一个整数表示所要求的最大值。 Sample Input 11 2 1 1 1 12 4 1 1 1 0 -3 1 Sample Output 4 Sample Explanation 对于这个序列，一个最佳的子序列是a1~ag，这个区间内"1"的个数是6，长度为8，受喜爱 程度为2*6-8=4，可以证明没有比这更大的值。 Hint 对于前50%的数据，n≤2000 对于100%的数据，n<=10^6，m<=1000,|a|<=10000
你刚学c，这个题绝对朝纲了，不过可以把代码发一下，我帮你优化
这道题应该用动态规划来作
那不是7个1么，怎么是6个？
#include<stdio.h>
#include <cstring>
#define max(a,b) (a>b?a:b)
int main(){
int n,m; scanf("%d %d",&n,&m);
int num[n+1];
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
int Max[n+1]; memset(Max,0,sizeof(Max));
int number=0, tnum[n+1][n+1]; //统计包括当前i元素往前的j个数字中连续的1的个数
memset(*tnum,0,sizeof(*tnum));
for(int i=1;i<=n;i++){ //每个数字 num[j]
if (num[i]==1) number=1;
else number=0;
memset(*(tnum+i),0,sizeof(*tnum));
tnum[i][1]=number;
for(int j=2;j<=n;j++){ //数量
if (j>i) break;
tnum[i][j] = number+tnum[i-1][j-1];
}
}
for(int i=1;i<=n;i++) //数量k
for(int j=1;j<=n;j++){ //每个数字 num[j]
if(i>j) continue;
Max[j] = max(Max[j],m*tnum[j][i]-i);
}
int ma=0;
for(int i=1;i<=n;i++)
if(Max[i]>ma) ma=Max[i];
printf("%d\n",ma);
return 1;
}
/*
11 2
1 1 1 12 4 1 1 1 0 -3 1
4
11 3
1 1 1 12 4 1 1 1 0 -3 1
10
12 3
1 1 1 12 4 1 1 1 0 -3 1 1
12
*/我做了一下，动态规划，复杂度是O(n*n)，我觉得也会超时。可能由于我初学动态规划没多久，只会几个案例。
我觉得想要降低时间消耗，需要直接从数据入手，根据m的大小找规律。但是感觉又挺复杂。
#include<stdio.h>
int a[1000000],s[1000000],b[1000000];
int main()
{
long int n,m,i=0,j=0,max=0,q=0;
scanf("%ld%ld",&n,&m);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
if(a[0]==0) printf("-1\n");
else{
for(i=0;i<n;i++)
{
if(a[i]==1)
{
if(j==0)
{
s[j]=1;
b[j]=i;
j++;
q++;
}
else
{
s[j]=s[j-1]+1;
b[j]=i;
j++;
q++;
}
}
}
j=0;
if(b[0]==0) max=m-1;
else max=-1;
if(q<=100000){
for(i=0;i<q-1;i++)
{
for(j=i+1;j<q;j++)
{
{
if(((j-i+1)*m-(b[j]-b[i]+1))>max) max=(j-i+1)*m-(b[j]-b[i]+1);
}
}
}
printf("%ld\n",max);}
else if(q==1000000)
{
printf("%ld\n",1000000*m-1000000);
}
else
{
for(i=0;i<q-1;i++)
{
for(j=i+1;j<q;j++)
{
{
if(((s[j]-s[i-1])*m-(b[j]-b[i]+1))>max) max=(s[j]-s[i-1])*m-(b[j]-b[i]+1);
}
}
}
printf("%ld\n",max);
}
}
}
#include<stdio.h>
#include <cstring>
#define max(a,b) (a>b?a:b)
int main(){
int n,m; scanf("%d %d",&n,&m);
int num[n+1];
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
int number;
int tnum[n+1]; //统计包括当前元素往前的数字中 连续的1的个数
memset(tnum,0,sizeof(tnum));
int Max[n+1]; memset(Max,0,sizeof(Max));
for(int i=1;i<=n;i++) //数量k
for(int j=1;j<=n;j++){ //每个数字 num[j]
if(i>j) continue;
if (num[j]==1) number=1;
else number=0;
tnum[j] = number+tnum[j-1];
Max[j] = max(Max[j],m*tnum[j]-i);
}
int ma=0;
for(int i=1;i<=n;i++)
if(Max[i]>ma) ma=Max[i];
printf("%d\n",ma);
return 1;
}我忘了可以用一维滚动数组了。现在数组是一维的应该不会出错了。
时间复杂度还是O(n*n)，你再试一试。
非常感谢您使用有问必答服务，为了后续更快速的帮您解决问题，现诚邀您参与有问必答体验反馈。您的建议将会运用到我们的产品优化中，希望能得到您的支持与协助！
速戳参与调研>>>https://t.csdnimg.cn/Kf0y
C和C++完整教程：https://blog.csdn.net/it_xiangqiang/category_10581430.html
您好，我是有问必答小助手，你的问题已经有小伙伴为您解答了问题，您看下是否解决了您的问题，可以追评进行沟通哦~
如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～
ps:问答VIP仅需29元，即可享受5次/月 有问必答服务，了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632