[Atcoder]ABC266题解

C - Convex Quadrilateral

计算几何

给定平面内四个点，要求判断它们组成的四边形是否是凸四边形

法一：

凸四边形的两条对角线将其分成两个三角形

分成的两个三角形面积相加等于四边形的面积

而显然这个结论对于凹四边形不成立

那么我们就可以利用这个结论进行解题

三角形面积用海伦公式求解

D - Snuke Panic(1D)

动态规划

设\(f[i][j]\)表示i时刻时在j位置的最大值\((j\in[0,4] \ \&\&\ i,j\in\textbf Z)\)

直接转移即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,f[100010][5],lst,ans=-1;
struct node
{
    int t,a,x;
}q[100010];
struct node2
{
    int a,x;
}w[100010];
signed main()
{
    scanf("%lld",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld %lld %lld",&q[i].t,&q[i].x,&q[i].a);
        w[q[i].t].a=q[i].a;
        w[q[i].t].x=q[i].x;
        lst=max(lst,q[i].t);
    }
    memset(f,-1,sizeof(f));
    f[0][0]=0;
    for (int i=1;i<=lst;i++)
    {
        for (int j=0;j<=4;j++)
        {
            if (j==0) f[i][j]=max(f[i-1][j],f[i-1][j+1]);
            else if(j==4) f[i][j]=max(f[i-1][j-1],f[i-1][j]);
            else f[i][j]=max(f[i-1][j-1],max(f[i-1][j],f[i-1][j+1]));
        }
        if (f[i][w[i].x]!=-1) f[i][w[i].x]+=w[i].a;
    }
    for (int i=0;i<=4;i++)
        ans=max(ans,f[lst][i]);
    printf("%lld",ans);
    //system("pause");
    return 0;
}