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

WBOY
リリース: 2016-06-24 12:01:13
オリジナル
1018 人が閲覧しました

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) 時間で取得できます。

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

れーい





関連ラベル:
ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート
私たちについて 免責事項 Sitemap
PHP中国語ウェブサイト:福祉オンライン PHP トレーニング,PHP 学習者の迅速な成長を支援します!