首页 > ACM题库 > HDU-杭电 > HDU 1223 Order Count-动态规划-[解题报告] C++
2013
12-04

HDU 1223 Order Count-动态规划-[解题报告] C++

Order Count

问题描述 :

If we connect 3 numbers with "<" and "=", there are 13 cases:
1) A=B=C
2) A=B<C
3) A<B=C
4) A<B<C
5) A<C<B
6) A=C<B
7) B<A=C
8) B<A<C
9) B<C<A
10) B=C<A
11) C<A=B
12) C<A<B
13) C<B<A

If we connect n numbers with "<" and "=", how many cases then?

输入:

The input starts with a positive integer P(0<P<1000) which indicates the number of test cases. Then on the following P lines, each line consists of a positive integer n(1<=n<=50) which indicates the amount of numbers to be connected.

输出:

For each input n, you should output the amount of cases in a single line.

样例输入:

2
1
3

样例输出:

1
13

Hint
Hint
Huge input, scanf is recommended.

http://acm.hdu.edu.cn/showproblem.php?pid=1223

  dp递推求满足条件的不等式的个数。

  这里需要用到大数乘法,于是我就顺便打了一个大数的模板,重载了+和*运算符。

  递推的公式很简单,dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * j,其中i 是指共有i 个符号,j 是指将i 个符号分成j 份,dp得到种类的数目。然后dp[i][1~i]各项相加,就是最终的答案了。

代码如下:

#include <cstdio>
 #include <cstring>
 #include <cstdlib>
 #include <cassert>
 #include <cmath>
 #include <algorithm>
 
 using namespace std;
 
 const int maxSize = 150;
 
 struct bigNum {
     char num[maxSize];
 };
 
 bigNum operator * (bigNum a, bigNum b) {
     int la = strlen(a.num);
     int lb = strlen(b.num);
     bigNum ret;
     int tmp[maxSize];
 
     for (int i = 0; i < la; i++) a.num[i] -= '0';
     for (int i = 0; i < lb; i++) b.num[i] -= '0';
     for (int i = 0, endi = la + lb; i <= endi; i++) tmp[i] = ret.num[i] = 0;
     for (int i = 0; i < la; i++) {
         int ti = la - 1 - i;
 
         for (int j = 0; j < lb; j++) {
             int tj = lb - 1 - j;
 
             tmp[i + j] += a.num[ti] * b.num[tj];
         }
     }
     for (int i = 0, endi = la + lb - 1; i < endi; i++) {
         tmp[i + 1] += tmp[i] / 10;
         ret.num[endi - i] = tmp[i] % 10 + '0';
     }
     ret.num[0] = tmp[la + lb - 2] / 10 + '0';
 
     if (ret.num[0] == '0') {
         for (int i = 1, endi = la + lb + 2; i < endi; i++) {
             ret.num[i - 1] = ret.num[i];
         }
     }
 
     return ret;
 }
 
 bigNum operator + (bigNum a, bigNum b) {
     int la = strlen(a.num);
     int lb = strlen(b.num);
     bigNum ret;
     int maxLen = max(la, lb);
     int minLen = min(la, lb);
 
     for (int i = 0; i <= maxLen + 1; i++) ret.num[i] = 0;
     for (int i = 0; i < minLen; i++) {
         ret.num[maxLen - i] += a.num[la - i - 1] + b.num[lb - i - 1] - '0';
         if (ret.num[maxLen - i] > '9') ret.num[maxLen - i - 1]++, ret.num[maxLen - i] -= 10;
     }
     if (maxLen == la) {
         for (int i = minLen; i < maxLen; i++) {
             ret.num[maxLen - i] += a.num[la - i - 1];
             if (ret.num[maxLen - i] > '9') ret.num[maxLen - i - 1]++, ret.num[maxLen - i] -= 10;
         }
     } else {
         for (int i = minLen; i < maxLen; i++) {
             ret.num[maxLen - i] += b.num[lb - i - 1];
             if (ret.num[maxLen - i] > '9') ret.num[maxLen - i - 1]++, ret.num[maxLen - i] -= 10;
         }
     }
     ret.num[0] += '0';
 
     if (ret.num[0] == '0') {
         for (int i = 1, endi = la + lb + 2; i < endi; i++) {
             ret.num[i - 1] = ret.num[i];
         }
     }
 
     return ret;
 
 }
 
 const int maxn = 52;
 bigNum dp[maxn][maxn];
 bigNum fac[maxn];
 
 char *con(int x) {
     int len = (int)log10((double)x) + 1;
     char *ret = new char[len + 1];
 
     for (int i = len - 1; i >= 0; i--) {
         ret[i] = x % 10 + '0';
         x /= 10;
     }
     ret[len] = 0;
 
     return ret;
 }
 
 void pre() {
     strcpy(fac[0].num, "1");
     for (int i = 1; i < maxn; i++){
         bigNum tmp;
         char *temp = con(i);
 
         strcpy(tmp.num, temp);
         delete temp;
         fac[i] = fac[i - 1] * tmp;
     }
     for (int i = 1; i < maxn; i++) {
         strcpy(dp[i][1].num, "1");
         strcpy(dp[i][i].num, "1");
         for (int j = 2; j < i; j++) {
             bigNum tmp;
             char *temp = con(j);
 
             strcpy(tmp.num, temp);
             delete temp;
             dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * tmp;
         }
         strcpy(dp[i][0].num, "0");
         for (int j = 1; j <= i; j++){
             dp[i][0] = dp[i][0] + dp[i][j] * fac[j];
         }
 //printf("%s\n", dp[i][0].num);
     }
 }
 
 int main() {
     pre();
     int n, T;
 
     scanf("%d", &T);
     while (T-- && ~scanf("%d", &n)){
         printf("%s\n", dp[n][0].num);
     }
 
     return 0;
 }

 

——written by Lyon


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!