组合数学第一发 hdu 2451 Simple Addition Expression - c++编程基础

efine PI acos(-1.0) #define maxn 15 #define INF 1<<25 typedef long long ll; using namespace std; int len; int nn[maxn]; int ans[maxn]; __int64 dfs(int pos,bool cmp) { if(pos==0) return 1; if(ans[pos]!=-1&&!cmp) return ans[pos]; int news=(cmp==1 nn[pos]:9); if(pos==1) news=min(news,2); else news=min(news,3); __int64 aa=0; for(int i=0;i<=news;i++) { bool c=(cmp&&(i==nn[pos])); aa+=dfs(pos-1,c); } return cmp aa:ans[pos]=aa; } int main() { __int64 num; while(scanf("%I64d",&num)!=EOF) { num--; memset(ans,-1,sizeof(ans)); int pp=0; while(num) { nn[++pp]=num%10; num/=10; } printf("%I64d\n",dfs(pp,1)); } } 因为是数论专题里的题，所以还是要用组合数学的想法去思考，从给的数字的最高位往下搞，刚开始不是很理解"组合"是什么意思。给出“组合数学”定义狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化（最佳组合）等。这题的组合数学就是组合的问题。刚开始想要从高位向低位一位一位搞，每搞一位算出后面对应所有可取的数后向后跳一位，直到最后一位。后来发现自己逗了，如果有某位数（最后一位除外）>=4时，即包括后面的所有情况，便需跳出循环，防止计算不应该计算的数。代码

#include
    
     
#include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #define PI acos(-1.0) #define maxn 15 #define INF 1<<25 typedef long long ll; using namespace std; int main() { __int64 tot; char num[15]; while(scanf("%s",num)!=EOF) { __int64 ans=0; int len=strlen(num); for(int i=0; i
               
                ='4') { ans+=pow(4.0,len-1-i)*3; break; } else ans+=pow(4.0,len-2-i)*3*(num[i]-'0'); } else { if(num[i]>='3') ans+=3; else ans+=num[i]-'0'; } } printf("%I64d\n",ans); } }

可能数据相对比较水的缘故，用两种算法提交都是15ms，不过用组合数学的方法明显时间复杂度比较低。

组合数学第一发 hdu 2451 Simple Addition Expression(二)