=num(b)>=num(c)解題思路:用dp[i][j][k]表示a取i個,b取j個,c取k個的狀態(tài)下最多有多少種滿足條件的情況,容易推得狀態(tài)轉(zhuǎn)移方程如下:dp[i][j][k]=dp[i-1][j][k](i>j時)+dp[i][j-1][k](" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

HDU 1502 Regular Words DP+高精度

系統(tǒng) 1647 0

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1502

題目大意:找出總的滿足條件的字符串?dāng)?shù),num(a)=num(b)=num(c)且任何前綴均滿足num(a)>=num(b)>=num(c)

解題思路:用dp[i][j][k]表示a取i個,b取j個,c取k個的狀態(tài)下最多有多少種滿足條件的情況,容易推得狀態(tài)轉(zhuǎn)移方程如下:

dp[i][j][k]=dp[i-1][j][k](i>j時)+dp[i][j-1][k](j>k時)+dp[i][j][k-1](k>0時)

根據(jù)該狀態(tài)轉(zhuǎn)移方程即可輸出最后的結(jié)果dp[n][n][n]

因為本題的數(shù)據(jù)結(jié)果比較大,所以還需要用到高精度,對不會用java的人就只能手敲一個大數(shù)相加了。。。

        
            1
        
         #include<cmath>


        
            2
        
         #include<cstdio>


        
            3
        
         #include<cstring>


        
            4
        
         #include<iostream>


        
            5
        
         #include<algorithm>


        
            6
        
        
          #define
        
         scan(a) scanf("%d",&a)


        
            7
        
        
          using
        
        
          namespace
        
        
           std;


        
        
            8
        
        
          #define
        
         N 61


        
            9
        
        
          char
        
         dp[N][N][N][
        
          100
        
        ],a[
        
          100
        
        
          ];


        
        
           10
        
        
          void
        
        
           init()


        
        
           11
        
        
          {


        
        
           12
        
             strcpy(dp[
        
          0
        
        ][
        
          0
        
        ][
        
          0
        
        ],
        
          "
        
        
          1\0
        
        
          "
        
        
          );


        
        
           13
        
             strcpy(dp[
        
          1
        
        ][
        
          1
        
        ][
        
          0
        
        ],
        
          "
        
        
          1\0
        
        
          "
        
        
          );


        
        
           14
        
             strcpy(dp[
        
          1
        
        ][
        
          0
        
        ][
        
          1
        
        ],
        
          "
        
        
          0\0
        
        
          "
        
        
          );


        
        
           15
        
             strcpy(dp[
        
          1
        
        ][
        
          0
        
        ][
        
          0
        
        ],
        
          "
        
        
          1\0
        
        
          "
        
        
          );


        
        
           16
        
        
          }


        
        
           17
        
        
           18
        
        
          void
        
         add(
        
          char
        
         *
        
          p)


        
        
           19
        
        
          {


        
        
           20
        
        
          int
        
         x,l,i,jin=
        
          0
        
        
          ;


        
        
           21
        
             l=
        
          strlen(a);


        
        
           22
        
        
          int
        
         now=
        
          0
        
        
          ;


        
        
           23
        
        
          for
        
        (i=
        
          0
        
        ;p[i]!=
        
          '
        
        
          \0
        
        
          '
        
        ;i++
        
          )


        
        
           24
        
        
          //
        
        
          從加數(shù)開始一位一位訪問
        
        
           25
        
        
              {


        
        
           26
        
        
          if
        
        (i>=
        
          l)


        
        
           27
        
                     x=p[i]-
        
          '
        
        
          0
        
        
          '
        
        +jin;
        
          //
        
        
          i超過了a的長度
        
        
           28
        
        
          else
        
        
           29
        
                     x=p[i]-
        
          '
        
        
          0
        
        
          '
        
        +a[i]-
        
          '
        
        
          0
        
        
          '
        
        +
        
          jin;


        
        
           30
        
        
          if
        
        (x>
        
          9
        
        
          )


        
        
           31
        
        
                  {


        
        
           32
        
                     jin=x/
        
          10
        
        
          ;


        
        
           33
        
                     x%=
        
          10
        
        
          ;


        
        
           34
        
        
                  }


        
        
           35
        
        
          else
        
        
           36
        
                     jin=
        
          0
        
        
          ;


        
        
           37
        
                 a[now++]=x+
        
          '
        
        
          0
        
        
          '
        
        
          ;


        
        
           38
        
        
              }


        
        
           39
        
        
          while
        
        
          (jin)


        
        
           40
        
        
              {


        
        
           41
        
        
          if
        
        (l<=
        
          now)


        
        
           42
        
        
                  {


        
        
           43
        
                     a[now++]=(jin%
        
          10
        
        )+
        
          '
        
        
          0
        
        
          '
        
        
          ;


        
        
           44
        
                     jin/=
        
          10
        
        
          ;


        
        
           45
        
        
                  }


        
        
           46
        
        
          else
        
        
           47
        
        
                  {


        
        
           48
        
                     x=a[now]-
        
          '
        
        
          0
        
        
          '
        
        
          ;


        
        
           49
        
                     x+=
        
          jin;


        
        
           50
        
        
          if
        
        (x>
        
          10
        
        
          )


        
        
           51
        
        
                      {


        
        
           52
        
                         jin=x/
        
          10
        
        
          ;


        
        
           53
        
                         x%=
        
          10
        
        
          ;


        
        
           54
        
        
                      }


        
        
           55
        
        
          else
        
        
           56
        
                         jin/=
        
          10
        
        
          ;


        
        
           57
        
                     a[now++]=x+
        
          '
        
        
          0
        
        
          '
        
        
          ;


        
        
           58
        
        
                  }


        
        
           59
        
        
              }


        
        
           60
        
        
          if
        
        (now>
        
          l)


        
        
           61
        
                 a[now]=
        
          '
        
        
          \0
        
        
          '
        
        
          ;


        
        
           62
        
        
          }


        
        
           63
        
        
           64
        
        
          void
        
         put(
        
          int
        
        
           x)


        
        
           65
        
        
          {


        
        
           66
        
        
          int
        
         l=
        
          strlen(dp[x][x][x]);


        
        
           67
        
        
          for
        
        (
        
          int
        
         i=l-
        
          1
        
        ;i>=
        
          0
        
        ;i--
        
          )


        
        
           68
        
                 cout<<
        
          dp[x][x][x][i];


        
        
           69
        
             cout<<endl<<
        
          endl;


        
        
           70
        
        
          }


        
        
           71
        
        
           72
        
        
          int
        
        
           main()


        
        
           73
        
        
          {


        
        
           74
        
        
          int
        
        
           i,j,k;


        
        
           75
        
        
          int
        
        
           n;


        
        
           76
        
        
              init();


        
        
           77
        
        
          for
        
        (i=
        
          1
        
        ;i<=
        
          60
        
        ;i++
        
          )


        
        
           78
        
        
              {


        
        
           79
        
        
          for
        
        (j=
        
          0
        
        ;j<=i;j++
        
          )


        
        
           80
        
        
                  {


        
        
           81
        
        
          for
        
        (k=
        
          0
        
        ;k<=j;k++
        
          )


        
        
           82
        
        
                      {


        
        
           83
        
                         a[
        
          0
        
        ]=
        
          '
        
        
          0
        
        
          '
        
        
          ;


        
        
           84
        
                         a[
        
          1
        
        ]=
        
          '
        
        
          \0
        
        
          '
        
        
          ;


        
        
           85
        
        
          //
        
        
           cout<<i<<' '<<j<<' '<<k<<endl;


        
        
           86
        
        
          //
        
        
           cout<<dp[i-1][j][k]<<' '<<dp[i][j-1][k]<<' '<<dp[i][j][k-1]<<endl;
        
        
           87
        
        
          if
        
        (i>j&&j>=
        
          k)


        
        
           88
        
                             add(dp[i-
        
          1
        
        
          ][j][k]);


        
        
           89
        
        
          if
        
        (j>
        
          k)


        
        
           90
        
                             add(dp[i][j-
        
          1
        
        
          ][k]);


        
        
           91
        
        
          if
        
        (k>
        
          0
        
        
          )


        
        
           92
        
                             add(dp[i][j][k-
        
          1
        
        
          ]);


        
        
           93
        
        
                          strcpy(dp[i][j][k],a);


        
        
           94
        
        
                      }


        
        
           95
        
        
                  }


        
        
           96
        
        
              }


        
        
           97
        
        
          while
        
        (~scanf(
        
          "
        
        
          %d
        
        
          "
        
        ,&
        
          n))


        
        
           98
        
        
              {


        
        
           99
        
        
                  put(n);


        
        
          100
        
        
              }


        
        
          101
        
        
          return
        
        
          0
        
        
          ;


        
        
          102
        
         }
      
View Code

?

?

HDU 1502 Regular Words DP+高精度


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。。?/p>

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 日本视频在线观看不卡高清免费 | 成人精品福利 | 四虎影视永久在线精品免费播放 | 久久精品视频3 | 国产精品免费精品自在线观看 | 久久99久久99精品免观看不卡 | 久久青草免费91观看 | 久草国产在线 | 国产精品久久久久无码av | 欧美性猛交ⅹxxx乱大交免费 | 精品小视频在线观看 | 国内精品久久久久影院嫩草 | 九九99久久精品国产 | 99热手机在线观看 | 国产精品久久久久无码av | 玖玖精品视频 | 美女国产精品 | 中文字幕日韩精品在线 | 真实国产精品视频国产网 | 久久99热精品这里久久精品 | 不卡中文字幕 | 久久国产区 | 国产dvd毛片在线视频 | 高清国产精品入口麻豆 | 亚洲综合色在线 | 久久毛片免费看一区二区三区 | 国产高清对白国产露脸91 | 午夜在线视频一区二区三区 | 男人都懂的网址 | 国产精品青草久久久久婷婷 | 九九精品视频在线观看九九 | 国产亚洲精品97在线观看 | 日本免费人成黄页网观看视频 | 伊人久久影院 | 久草精彩视频 | 成人婷婷| 快射影院| 午夜色大片在线观看 | 国产乱色| 欧美日本成人 | 中文字幕日韩一区二区不卡 |