两道不错的递推dp

hdoj-4055

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int mod=;

const int N=+;

long long sum[N][N];

char str[N];

int main ()

{

    // 含义 dp[i][j] 前i个字母 以数字j结尾的排列方式 比如("II"）-dp[2][3] 表示 “123”

    //递推公式 如果str="I" dp[i][j]=dp[i-1][1]+dp[i-1][2]+...+dp[i-1][j-1];

            //str="D"     dp[i][j]=dp[i-1][j]+dp[i][j+1]+...+dp[i][i+1]

           // 解释比如前i-1个排列 {3 1 4 2 5}    可以加一个 3 前面所有比3大的数加1（这样不会改变前面的增长顺序）

           // 变成{4，1，5，2，6，3}

   //sum[i][j]=dp[i][1]+dp[i][2]+...dp[i][j];

    while (~scanf (" %s",str+)) {

        int n=strlen(str+);

        sum[][]=;

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

            for (int j=;j<=i+;j++) {//i+1  因为i个字母表示i+1个数字

                sum[i][j]=sum[i][j-];

                if (str[i]!='D')

                    sum[i][j]+=sum[i-][j-];

                if (str[i]!='I')

                    sum[i][j]+=sum[i-][i]-sum[i-][j-]+mod;

                sum[i][j]%=mod;

            }

        }

        printf ("%lld\n",sum[n][n+]);

    }

    return ;

}

hdoj-4489

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

LL dp[][];

LL f (int n,int m) {  // f: C(n,m)

    LL ans=;

    if (m==) return ;

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

        ans*=i;

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

        ans/=i;

    return ans;

}

int main ()

{

  dp[][]=dp[][]=;

  dp[][]=dp[][]=;// 在前i个数排好基础下排第j个

                      // dp[i][0] 以下降方式结尾  dp[i][1]以上升方式开始

                      // 第i个数排在下降方式结尾子序列和以上升方式开始子序列之间

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

        LL tmp=;

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

        tmp+=dp[j][]*dp[i--j][]*f(i-,j);

    dp[i][]=dp[i][]=tmp/;

  }

  int T;

  scanf ("%d",&T);

  while (T--) {

    int x,n;

    scanf ("%d %d",&x,&n);

    if (n==) printf ("%d 1\n",x);// 注意这个特殊情况

    else      printf ("%d %lld\n",x,*dp[n][]);

  }

  return ;

}