题目描述
对于任意整数n($1≤n≤4⋅10^4$ ),求将它拆解成回文数之和的方案个数。
样例说明
input = 5
5=1+1+1+1+1
5=1+1+1+2
5=1+2+2
5=1+1+3
5=2+3
5=1+4
5=5
output = 7
分析
由于数据范围比较小,我们可以预处理出范围内的所有回文数,然后使用动态规划求解。
状态表示
f[i] :将i拆解成多个回文数相加的方案的集合
属性:Count
状态计算:
f[i] += f[i - k];// k为小于i的所有回文数
C++ code
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 10,mod = 1e9+7;
int f[N];
vector<int> alls;// 存储所有回文数
bool ispalin(int x){//判断一个数是否是回文数
int res = 0;
int y = x;
while(y){
res*= 10;
res += y %10;
y /= 10;
}
return res == x;
}
int main()
{
int n,cases;
cin >> cases;
for(int i = 0; i <= N ; ++i){//预处理所有回文数
if(ispalin(i))alls.push_back(i);
}
f[0] = 1;
for(int i = 1; i < alls.size(); ++i){//预处理出数据范围内的所有方案
for(int j = alls[i]; j <= 40001; ++j){//这里j 取到40010就跑不动了
f[j] += f[j - alls[i]];
f[j] %= mod;
}
}
while(cases--){
int t;cin >> t;
cout << f[t] << endl;
}
return 0;
}