題目鏈接: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 }
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

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