UVA - 11375 Matches(高精度，递推)

矫情吗；* 2022-06-09 00:12 178阅读 0赞

![Center][]

题意：这道题就是给N个火柴棍，问你用它们最多能组成多少种数，比如说3根火柴棍只能组合成1和7两种，因为1需要两根火柴，7需要三根火柴，其他都需要四根及以上。4根火柴则可以组合成1，7，4，11这四种。

思路：这题可以用DP做，但是也可以直接根据递推关系得出答案。当你有N个火柴的时候，第一个数可以摆如果摆1，那么你就会剩下N-2个火柴，如果摆7，那么你就会剩下N-3个火柴，如果摆4，那么你就会剩下N-4个火柴，如果摆2，3，5，那么你就会剩下N-5个火柴，如果摆0，6，9，那么你就会剩下N-6个火柴，如果摆8，那么就会剩下N-7个火柴。

依此类推，a\[N\]=a\[N-2\]+a\[N-3\]+a\[N-4\]+3\*a\[N-5\]+3\*a\[N-6\]+a\[N-7\]，递推式很简单就出来了，此处的a\[N\]是指恰好用了N根火柴，不多不少时，所能组成的数的个数。那么答案就只需要再记录一个前缀和就行了。但是这里有一点要注意，就是前导零的问题，在求递推式的时候，我们要记录两种结果，一种是+2\*a\[N-6\],一种是+3\*a\[N-6\]，2倍的a\[N-6\]就是考虑了前导零的情况，那么当前考虑的这个数必然在第一位，所以这个数值是应该存入答案数组的值，而3倍的a\[N-6\]是没考虑前导零的，那么说明它不在第一位，是计算后面的a\[N\]时所需要用到的，所以这个数值应该存入递推关系的数里。如果没有理解的话，看代码就能理解了，注意使用高精度。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 105;
    const int MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    string ans[2005];
    const int L = 1100;
    string mul(string a, string b)//高精度乘法a,b,均为非负整数  
    {
    	string s;
    	int na[L], nb[L], nc[L], La = a.size(), Lb = b.size();//na存储被乘数，nb存储乘数，nc存储积  
    	fill(na, na + L, 0); fill(nb, nb + L, 0); fill(nc, nc + L, 0);//将na,nb,nc都置为0  
    	for (int i = La - 1; i >= 0; i--) na[La - i] = a[i] - '0';//将字符串表示的大整形数转成i整形数组表示的大整形数  
    	for (int i = Lb - 1; i >= 0; i--) nb[Lb - i] = b[i] - '0';
    	for (int i = 1; i <= La; i++)
    		for (int j = 1; j <= Lb; j++)
    			nc[i + j - 1] += na[i] * nb[j];//a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位）  
    	for (int i = 1; i <= La + Lb; i++)
    		nc[i + 1] += nc[i] / 10, nc[i] %= 10;//统一处理进位  
    	if (nc[La + Lb]) s += nc[La + Lb] + '0';//判断第i+j位上的数字是不是0  
    	for (int i = La + Lb - 1; i >= 1; i--)
    		s += nc[i] + '0';//将整形数组转成字符串  
    	return s;
    }
    
    string add(string a, string b)//只限两个非负整数相加  
    {
    	string ans;
    	int na[L] = { 0 }, nb[L] = { 0 };
    	int la = a.size(), lb = b.size();
    	for (int i = 0; i<la; i++) na[la - 1 - i] = a[i] - '0';
    	for (int i = 0; i<lb; i++) nb[lb - 1 - i] = b[i] - '0';
    	int lmax = la>lb ? la : lb;
    	for (int i = 0; i<lmax; i++) na[i] += nb[i], na[i + 1] += na[i] / 10, na[i] %= 10;
    	if (na[lmax]) lmax++;
    	for (int i = lmax - 1; i >= 0; i--) ans += na[i] + '0';
    	return ans;
    }
    
    void init()
    {
    	string a1, a2, a3, a4, a5, a6, a7, a8, t,t1,t2 ,b3, b2;
    	b3 = "3";
    	b2 = "2";
    	a1 = "0";//递推关系的前几位不能靠关系式得出，手动计算出来
    	a2 = "1";
    	a3 = "1";
    	a4 = "2";
    	a5 = "5";
    	a6 = "7";
    	a7 = "12";
    	a8 = "20";
    	ans[1] = "0";
    	ans[2] = "1";
    	ans[3] = "2";
    	ans[4] = "4";
    	ans[5] = "9";
    	ans[6] = "16";
    	ans[7] = "28";
    	ans[8] = "47";
    	for (int i = 9; i <= 2000; i++)
    	{
    		t = "0";
    		t1 = "0";
    		t2 = "0";
    		t = add(t, a7);
    		t = add(t, a6);
    		t = add(t, a5);
    		t = add(t, mul(a4, b3));
    		t1 = add(t, mul(a3, b3));//存入递推关系的值，不用考虑前导零，因为该数不会作为第一位。
    		t2 = add(t, mul(a3, b2));//存入答案的值，要考虑前导零，因为此时是第一位。
    		t2 = add(t2, a2);
    		t1 = add(t1, a2);
    		ans[i] = add(ans[i - 1], t2);
    		a1 = a2;
    		a2 = a3;
    		a3 = a4;
    		a4 = a5;
    		a5 = a6;
    		a6 = a7;
    		a7 = a8;
    		a8 = t1;
    	}
    }
    
    int main()
    {
    	init();
    	int s;
    	while (scanf("%d",&s)!=EOF)
    	{
    		cout << ans[s] << endl;
    	}
    }

[Center]: /images/20220609/19a5f49c7b664c8498f8fd4c8917f1a2.png