CF 1016 C —— 思路

题目：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 ;

}