[CF][思维][预处理][枚举] CF1016C Vasya And The Mushrooms

这场CF也是崩了。。AB太慢而且wa了n发,C知道正确做法然后wa了3发剩20min放弃了。然后今天手算了五分钟ac emmmmm

这个要做到每个格子都只走一次,就必须先蛇形然后转圈,只不过中间从哪一点开始转圈决定了最后的答案大小。样例给的就是两种极端情况,一种是从一开始就开始转圈,另一种是一直蛇形直到最后。

预处理的话左边的从左往右推,右边的从右往左推,主要是右边的计算有点绕(其实也不是很绕主要是当时心态崩了emmm

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include

using namespace std;
typedef long long LL;
const int maxn=1e6+5;
const int MOD=1e9+7;


LL board[2][maxn],dpl[maxn],dpr0[maxn],dpr1[maxn],sur[maxn];

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int n;
    LL res=0;
    scanf("%d",&n);

    for (int i=0;i<2;i++)
    {
        for (int j=1;j<=n;j++)
            scanf("%d",&board[i][j]);
    }
    for (int i=n;i>0;i--)
        sur[i]+=sur[i+1]+board[0][i]+board[1][i];
    for (int i=1;i<=n;i++)
    {
        if(i%2)
            dpl[i]=dpl[i-1]+2*(i-1)*board[0][i]+(2*i-1)*board[1][i];
        else
            dpl[i]=dpl[i-1]+2*(i-1)*board[1][i]+(2*i-1)*board[0][i];
    }
    for (int i=n;i>0;i--)
    {
        dpr0[i]=dpr0[i+1]-sur[i+1]+2*(i-1)*board[0][i]+(2*n-1)*board[1][i];
    }
    for (int i=n;i>0;i--)
    {
        dpr1[i]=dpr1[i+1]-sur[i+1]+2*(i-1)*board[1][i]+(2*n-1)*board[0][i];
    }
    for(int i=1;i<=n;i++)
    {
        if(i%2)
            res=max(dpr0[i]+dpl[i-1],res);
        else
            res=max(dpr1[i]+dpl[i-1],res);

    }
    cout<
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据