本文主要是介绍UVa 11375 Matches，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
大年夜的写代码果然状态非常之差...感觉特别困，连个高精度都折腾了我好久。还是刘汝佳《训练指南》里的一道例题，解题思路其实也差不多，但是想对书里面的内容再讲讲。其中d[i]是代表i个火柴棒恰好能构成的正整数数目（不包含整数0），然后有点类似于动态规划的做法，通过已知的d[]求出剩下的d[]。
不过仔细想来貌似有点问题。例如已知d[j]，那么d[j+num[0]]+=d[j].那么新加的数字0是不是应该也有好几种排列方式呢？例如d[j]中有一个数字123，那么d[j+num[0]]是不是应该有1230,1203,1023...等等各种方式呢？其实不是的d[j+num[0]]+=d[j]这个式子其实都是在数的末尾添加新数字的。123新增一个0就是1230，而1203则是120新加一个3完成的。所以，!(i==0&&j==0)就可以理解了。第一个数字不能是0，否则会产生前置0的问题。至于那个整数0，在N>=6时，每个答案都要加上1。
头有点晕，哈哈哈，写得可能不是很清楚，具体还是参考代码吧！另：用string还是会超时，可能是由于频繁的内存分配问题....
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#define MAX 2000+5
#define MAXL 1000
using namespace std;char d[MAX][MAXL],ans[MAX][MAXL];//d[i]为恰好用i根火柴棍能完成的正整数，ans[i]为最后的解答
int dlen[MAX],alen[MAX];//dlen[i]对应字符串d[i]的长度，alen同理对应ans
int num[10]={6,2,5,5,4,5,6,3,7,6};//10个数字对应的火柴棍数void add(int&,int,char*,const char*);
int main()
{d[0][0]='1',dlen[0]=1;d[1][0]='0',dlen[1]=1;//这里必须要初始化，否则按照下述高精度方式，ans[i]可能会产生空for(int i=0;i<MAX;++i){for(int j=0;j<10;++j){if(!(i==0&&j==0)&&i+num[j]<MAX) add(dlen[i+num[j]],dlen[i],d[i+num[j]],d[i]);}}for(int i=1;i<MAX;++i){for(int j=1;j<=i;++j) add(alen[i],dlen[j],ans[i],d[j]);if(i>=6) add(alen[i],1,ans[i],"1");//火柴棍数大于6，结果要加1}int N;while(cin>>N){int pos;for(pos=alen[N]-1;pos>=0;--pos) cout<<ans[N][pos];cout<<endl;}return 0;
}void add(int& la,int lb,char* a,const char* b)//高精度运算
{int len;len=max(la,lb);int sum,overflow=0;for(int i=0;i<len;++i){if(lb<=i){//被加的字符长度不足sum=a[i]-'0'+overflow;}else{if(la<=i){a[i]='0';++la;}//加的字符串长度不足，且长度值需修改sum=a[i]-'0'+b[i]-'0'+overflow;}a[i]=sum%10+'0';overflow=sum/10;}if(overflow){//还有进位a[la++]=overflow+'0';}return;
}
这篇关于UVa 11375 Matches的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
