题目链接
大意：给一个数n，1~n中的一些回文数相加和有等于n的情况，求这个情况数。回文数可以重复出现。不考虑回文数相加的顺序。
时限2s，n<=4e4。
这题看完题解才能写。这个dp方法绝对值得记住，好像还是个通用的类型，划分问题？下次遇到再推广吧。看完题解后还在卡，主要卡在一开始的N没有算对，应该是498但是写成300，只考虑了5位回文数个数也是牛的啊我。还有边界赋值的问题，下次再迷糊就从第一个有意义的dp[i][j]开始一个一个演草，找出来需要考虑的边界就行了，别在那形而上了，好累还慢。
解析：4e4以内的回文数很少，五位回文数300个，四、三、二、一位回文数分别为90、90、9、9个。总共498个，记为M。把它们记录在p[]数组中之后，就可以使用DP实现的统计划分数来解决。时间复杂度O(M*N）。
dp[k][m]为前m个回文数中，加和为k的情况数。状态转移公式为dp[k][m]=dp[k][m-1]+dp[k-p[m]][m]。也就是说，前m个回文数中，加和为k的情况数=前m-1个回文数加和为k的情况数+前m个回文数加和为k且一定有至少一个第m个回文数出现的情况数。注意，前m个数不一定全都用到。边界初始化dp[0][i]=1,i从1到M。
判断一个数是否是回文串的写法很妙。将一个数的每一位放在对称的位置上形成一个新的数字，如果这个新数和原来相等，则为回文数。写法如下：
for(int i=1;i<=N;i++){
//s=i+"";
//int len=s.length()>>1;
//boolean flag=false;
int r=0;
int x=i;
while(x>0){
r=r*10+x%10;
x/=10;
//System.out.println(i);
}
if(r==i){
p[cnt++]=i;
}
}
本题AC代码：
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main2 {
static InputReader2 sc=new InputReader2(System.in);
/* static int MAXN=200005,n,m,a[]=new int[MAXN],dp[]=new int[MAXN],edge[][]=new int[MAXN][2];
static long k;
static boolean vis[]=new boolean[MAXN],ok=false;
static Vector<Integer> G[]=new Vector[MAXN],g[]=new Vector[MAXN];*/
public static void main(String args[]){
solve();
}
private static void solve() {
//System.out.println(Integer.MAX_VALUE);
int M=500,N=40005;
int dp[][]=new int[N][M];
int p[]=new int[N];
int mod=1000000007;
String s="";
int cnt=1;
for(int i=1;i<=N;i++){
//s=i+"";
//int len=s.length()>>1;
//boolean flag=false;
int r=0;
int x=i;
while(x>0){
r=r*10+x%10;
x/=10;
//System.out.println(i);
}
if(r==i){
p[cnt++]=i;
}
}
//dp[1][1]=1;
for(int i=1;i<M;i++){
dp[0][i]=1;
}
/* for(int i=0;i<N;i++){
dp[i][0]=1;
}*/
for(int i=1;i<N;i++){
for(int j=1;j<M;j++){
//if(i==1&&j==1)continue;
if(i-p[j]<0){
dp[i][j]=dp[i][j-1];
}else dp[i][j]=(dp[i][j-1]+dp[i-p[j]][j])%mod;
//System.out.println(dp[i][j]+" "+i+" "+j+" "+p[j]);
}
}
//System.out.println(dp[1][1]);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
System.out.println(dp[n][M-1]);
}
}
}
class InputReader2 {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader2(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}