AtCoder Grand Contest 030 自闭记

　　A：阅读。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int a,b,c;

int main()

{

    a=read(),b=read(),c=read();

    cout<<b+min(c,a+b+);

    return ;

}

　　B：一个显然的做法是设f[i][j][0/1]为已经砍掉了1~i和j~n的树且停在左/右边的最长路，类似区间dp转移即可。因为开始头铁想了会正解和初始化出了些锅，很久之后才过掉这个部分分。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 200010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,a[N];

ll ans,f[][][];

int main()

{

    m=read(),n=read();

    for (int i=;i<=n;i++) a[i]=read();a[n+]=m;

    memset(f,,sizeof(f));

    f[][n+][]=a[],f[][n][]=m-a[n];

    for (int i=;i<=n;i++)

        for (int j=;j<=i;j++)

        {

            if (j) f[j][n+-(i-j)][]=max(f[j-][n+-(i-j)][]+a[j]-a[j-],f[j-][n+-(i-j)][]+a[j]+m-a[n+-(i-j)]);

            if (j<i) f[j][n+-(i-j)][]=max(f[j][n+-(i-j)][]+a[n+-(i-j)]-a[n+-(i-j)],f[j][n+-(i-j)][]+a[j]+m-a[n+-(i-j)]);

        }

    for (int i=;i<=n;i++) ans=max(ans,f[i][i+][]),ans=max(ans,f[i][i+][]);

    cout<<ans;

    return ;

}

　　脑补一下正解，考虑效果相同的两种走法：顺逆顺、逆顺顺，容易发现第一种总是比第二种优，这说明一旦某次改变方向，之后每次都要改变方向才能保证最优。于是枚举一下最开始怎么走，对每种方案求一下取max即可。

　　然后因为一些原因也没什么心思想题，就这么心态平稳地自闭到结束了。根本没脸写这玩意了题过会再补

　　result：rank 312 rating +56 怎么打成什么样都涨分啊？

　　upd：咕咕咕