题目:http://codeforces.com/contest/1016/problem/C

一定是先蛇形走在回形走,所以预处理、暴力即可;

自己一开始写了一个,总是WA,又看了看TJ写法;

模仿一下,还是WA,发现中间的一些地方 int 相乘要加 (ll)!

然后把我原来那个改一下就A了...

20分钟写,60分钟调...

不过模仿的那个写法比我原来的快多了(虽然做法一样)。

模仿:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const maxn=3e5+;
int n,g[][maxn];
ll s[][maxn],f[][maxn][],ans;
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)scanf("%d",&g[][i]);
for(int i=;i<n;i++)scanf("%d",&g[][i]);
for(int j=;j<=;j++)
for(int i=n-;i>=;i--)
{
f[j][i][]=f[j][i+][]+(ll)(n-i-)*g[j][i];//<-
f[j][i][]=f[j][i+][]+(ll)i*g[j][i];//-> //走过来一定在 i 时间或以后
s[j][i]=s[j][i+]+g[j][i];
}
ll w=,add=;
for(int x=,y=;x<n;x++,y^=)
{
add=x*s[y][x]+f[y][x][]+(x+n)*s[!y][x]+f[!y][x][];
ans=max(ans,w+add);
w+=(ll)g[y][x]**x+(ll)g[!y][x]*(*x+);
}
printf("%I64d\n",ans);
return ;
}

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const maxn=3e5+;
int n,g[][maxn];
ll s[][maxn],f[][maxn][],ans;
void dfs(int x,int y,ll w)
{
if(x==n)return;
ll t=*x,tt=t+n-x;
ans=max(ans,w+t*s[y][x+]+f[y][x+][]+tt*s[!y][x+]+f[!y][x+][]);
dfs(x+,y^,w+(ll)(t+)*(g[][x+]+g[][x+])+g[!y][x+]);
}
int main()
{
cin>>n;
for(int i=;i<=n;i++)cin>>g[][i];
for(int i=;i<=n;i++)cin>>g[][i];
for(int j=;j<=;j++)
{
for(int i=n,k=;i;i--,k++)
{
f[j][i][]=f[j][i+][]+(ll)k*g[j][i];//<-
s[j][i]=s[j][i+]+g[j][i];
}
for(int i=n;i;i--)
{
f[j][i][]=f[j][i+][]+s[j][i];//->
}
}
dfs(,,);
cout<<ans-s[][]-s[][];
return ;
}
05-28 07:16