两道不错的递推dp

hdoj-4055

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod=1000000007;
const int N=1000+7;
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+1)) {
        int n=strlen(str+1);
        sum[0][1]=1;
        for (int i=1;i<=n;i++)  {
            for (int j=1;j<=i+1;j++) {//i+1  因为i个字母表示i+1个数字
                sum[i][j]=sum[i][j-1];
                if (str[i]!='D')
                    sum[i][j]+=sum[i-1][j-1];
                if (str[i]!='I')
                    sum[i][j]+=sum[i-1][i]-sum[i-1][j-1]+mod;
                sum[i][j]%=mod;
            }
        }
        printf ("%lld
",sum[n][n+1]);
    }
    return 0;
}

hdoj-4489

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL dp[50][2];
LL f (int n,int m) {  // f: C(n,m)
    LL ans=1;
    if (m==0) return 1;
    for (int i=n-m+1;i<=n;i++)
        ans*=i;
    for (int i=1;i<=m;i++)
        ans/=i;
    return ans;
}
int main ()
{
  dp[0][0]=dp[0][1]=1;
  dp[1][0]=dp[1][1]=1;// 在前i个数排好基础下排第j个
                      // dp[i][0] 以下降方式结尾  dp[i][1]以上升方式开始
                      // 第i个数排在下降方式结尾子序列和以上升方式开始子序列之间
  for (int i=2;i<=20;i++) {
        LL tmp=0;
    for (int j=0;j<i;j++)
        tmp+=dp[j][0]*dp[i-1-j][0]*f(i-1,j);
    dp[i][0]=dp[i][1]=tmp/2;
  }
  int T;
  scanf ("%d",&T);
  while (T--) {
    int x,n;
    scanf ("%d %d",&x,&n);
    if (n==1) printf ("%d 1
",x);// 注意这个特殊情况
    else      printf ("%d %lld
",x,2*dp[n][0]);
  }
  return 0;
}