8.9
wave
【题目描述】
海浪分为前浪和后浪，分别用数字 0 和数字 1 表示。 现在给定一天中 n 个时段的海浪序列，第 i 个序列包含 $m_i$ 个海浪。 全天海浪序列是 n 个时段的海浪序列按照任意的一种次序顺次拼接而成的序列。 一个涨潮定义为海浪序列的一个子序列（不必连续），满足这个子序列中的任何一个前浪 都出现在任何一个后浪之前。涨潮的强度定义为其中包含的海浪个数。 请你求出所有可能的全天海浪序列中，强度最大的涨潮的强度最大值。【输入格式】
从文件 wave.in 中读入数据。 第一行一个正整数 n，表示序列个数。 接下来 n 行，第 i + 1 行一个正整数 $m_i$，其后紧随 $m_i$ 个数字 0 或 1，描述了一个海浪 序列。【输出格式】
输出到文件 wave.out 中。 第一行一个正整数，表示强度最大的涨潮的强度。\(solution\)
考虑每一个海浪序列全是1或者全是0所提供的最大贡献，与这个序列在中间的最大涨潮度相比较，保证所有序列的贡献加起来最大
AC Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=5e5+5;
int n,sum[N],s[N],sum1[N],ans=0;
int m0[N],m1[N],sum2[N];
int main()
{
// freopen("wave.in","r",stdin);
// freopen("wave.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
{
sum[i]=read();sum[i]+=sum[i-1];
for(int j=sum[i-1]+1;j<=sum[i];j++)
{
s[j]=read();
if(s[j]==0)m0[j]=m0[j-1]+1,m1[j]=m1[j-1];
else m1[j]=m1[j-1]+1,m0[j]=m0[j-1];
}
sum1[i]=max(m0[sum[i]]-m0[sum[i-1]],m1[sum[i]]-m1[sum[i-1]]);
sum2[i]=sum2[i-1]+sum1[i];
int tmp=0;
ans=max(ans,m0[sum[i]]-m0[sum[i-1]]-sum1[i]);
for(int j=sum[i];j>sum[i-1];j--)
{
if(s[j]==1)tmp++;
ans=max(ans,tmp+m0[j-1]-m0[sum[i-1]]-sum1[i]);
}
}
printf("%d\n",ans+sum2[n]);
return 0;
}
scientist
\(solution\)
50pts:
枚举通知的据点 T，那么第 i 个据点的人会在 \(f_{T (i)} = a_i + |T − i|\) 分钟结束时到达道路上。所以当j > fT (j)时，送货的人会被挡住。
又因为送货的人可能在被挡住之前，他的左右两侧都有人，所以目标达成的时间为：
\[max(min_{1\leq i < j}{f_{T(i)}},min_{j\leq i \leq n}{f_{T(i)}}) \]