UVALive 7276 Wooden Signs

详细题目见：http://7xjob4.com1.z0.glb.clouddn.com/0f10204481da21e62f8c145939e5828e

思路：记dp[i][j]表示第i个木板尾部在j的方案数。那么对于i+1,可以分三种情况讨论，一种是i+1的头部在第i根整段的左边，一种是在右边，还有在中间，中间的有两种情况，其他都只有一种，然后就可以转移了。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

typedef long long ll;

#define inf 99999999

#define pi acos(-1.0)

#define MOD 2147483647

#define maxn 2050

ll a[maxn],dp[maxn][maxn];

int main()

{

    ll n,m,i,j,c;

    ll l,r;

    while(scanf("%lld",&n)!=EOF)

    {

        scanf("%lld",&c);

        for(i=1;i<=n;i++){

            scanf("%lld",&a[i]);

        }

        memset(dp,0,sizeof(dp));

        dp[1][c]=1;

        for(i=1;i<=n-1;i++){

            for(j=1;j<=n+1;j++){

                if(dp[i][j]){

                    l=a[i];r=j;

                    if(l>r)swap(l,r);

                    if(a[i+1]<=l){

                        dp[i+1][r ]=(dp[i+1][r ]+dp[i][j])%MOD;

                    }

                    else if(a[i+1]>=r){

                        dp[i+1][l ]=(dp[i+1][l ]+dp[i][j] )%MOD;

                    }

                    else{

                        dp[i+1][r ]=(dp[i+1][r ]+dp[i][j])%MOD;

                        dp[i+1][l ]=(dp[i+1][l ]+dp[i][j] )%MOD;

                    }

                }

            }

        }

        ll sum=0;

        for(j=1;j<=n+1;j++){

            sum=(sum+dp[n][j])%MOD;

        }

        printf("%lld\n",sum);

    }

    return 0;

}

巴特西

UVALive 7276 Wooden Signs

最新文章

热门文章