[数据结构与算法] Palindrome Basis（完全背包）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Palindrome Basis（完全背包） -> 正文阅读

[数据结构与算法]Palindrome Basis（完全背包）

作者:recommend-item-box type_blog clearfix

LINK

题目：

在这里插入图片描述

大致翻译：

一个数字由数字回文串相加，问有多少种组合情况。

思路：

由完全背包可得：
$d p [i] [j] :$ 前 $i$ 个物品随意取，组成总体积为 $j$ 的方法数。
由此思路可得前 $i$ 个回文数里，相加之和为 $j$ 的方法数。
再转换为一维可得：
转换公式为：

dp[j]=(dp[j]+dp[j-v[i]])%mod;

代码：

#include <bits/stdc++.h>
using namespace std;
//#define ll long long
#define int long long
const int N=1e5+10;
const int NB=64;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
vector<int>v;
void init(){
	string s,ss;
	for(int i=0;i<=4e4;i++){
		s=ss=to_string(i);
		reverse(s.begin(),s.end());
		if(s==ss){
			v.push_back(i);
		}
	}
}
int dp[N];
signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	init();
	dp[0]=1;
	for(int i=1;i<v.size();i++){
		for(int j=v[i];j<=4e4;j++){
			dp[j]=(dp[j]+dp[j-v[i]])%mod;
		}
	}
	int t,n;cin>>t;
	while(t--){
		cin>>n;
		cout<<dp[n]<<endl;
	}
	return 0;
}