コードフォース ラウンド #FF (ディビジョン 1)-A、B、C_html/css_WEB-ITnose

A:DZY はシーケンスが大好きです

最初は間違った質問を読みました。 。悲しい。

質問はとても簡単で、方法もとても簡単です。それをDPするだけです。

dp[i][0]: 現在位置から数値を変更せずに取得した長さ。

dp[i][1]: 現在の位置に移動し、数値を変更し、長さを取得します

ただし、一度順方向に見つけてから、次に逆方向に見つける必要があります。

rrreeB: DZY は修正が大好きです

水平行を選択すると、垂直行のサイズ順序は変更されませんが、各垂直行が p ずつ減少することがわかります。

したがって、x 個の水平行と y 個の垂直行を列挙して選択できます。

#include<iostream>#include<stdio.h>#include<algorithm>#include<stdlib.h>#include<string.h>using namespace std;#define maxn 110000int dp[maxn][3];int num[maxn];int a[maxn];int n;void dos(int maxx){    memset(dp,0,sizeof(dp));    memset(num,-1,sizeof(num));    for(int i=n; i>=1; i--)    {        if(a[i]<a[i+1])        {            dp[i][0]=dp[i+1][0]+1;        }        else        {            dp[i][0]=1;        }        dp[i][1]=dp[i][0];        num[i]=a[i];        if(a[i]<num[i+1])        {            if(dp[i][1]<dp[i+1][1]+1)            {                dp[i][1]=dp[i+1][1]+1;                num[i]=a[i];            }        }        if(a[i]>=a[i+1])        {            if(dp[i][1]<dp[i+1][0]+1)            {                dp[i][1]=dp[i+1][0]+1;                num[i]=a[i+1]-1;            }        }    }    for(int i=1; i<=n; i++)    {         //cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<num[i]<<endl;        maxx=max(maxx,dp[i][0]);        maxx=max(maxx,dp[i][1]);    }    cout<<maxx<<endl;}int main(){    while(~scanf("%d",&n))    {        for(int i=1; i<=n; i++)        {            scanf("%d",&a[i]);        }        memset(dp,0,sizeof(dp));        memset(num,-1,sizeof(num));        for(int i=1; i<=n; i++)        {            if(a[i]>a[i-1])            {                dp[i][0]=dp[i-1][0]+1;            }            else            {                dp[i][0]=1;            }            dp[i][1]=dp[i][0];            num[i]=a[i];            if(a[i]>num[i-1])            {                if(dp[i][1]<dp[i-1][1]+1)                {                    dp[i][1]=dp[i-1][1]+1;                    num[i]=a[i];                }            }            if(a[i]<=a[i-1])            {                if(dp[i][1]<dp[i-1][0]+1)                {                    dp[i][1]=dp[i-1][0]+1;                    num[i]=a[i-1]+1;                }            }        }        int maxx=-1;        for(int i=1; i<=n; i++)        {            // cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<num[i]<<endl;            maxx=max(maxx,dp[i][0]);            maxx=max(maxx,dp[i][1]);        }        dos(maxx);    }    return 0;}

C: DZY はフィボナッチ数が大好きです

主に次の 2 つの特性によるものです: 2 つのフィボナッチ数を加算しても 1 つのフィボナッチ数になります。

2. フィボナッチ数列の最初の 2 つの項によれば、任意の位置のフィボナッチ数と任意の長さのフィボナッチ数列の合計を O(1) 時間で取得できます。

残りは単純な区間合計の問題です。

れーい