分析：这道题难度和天天爱跑步差不了多少啊......裸的暴力只有10分，最好大的还是那个5%的数据，不过这也才15分，比天天爱跑步的暴力分不知道少到哪里去了.
正解是dp,毕竟要求方案数嘛，但是这个dp非常不好想.设f[i][j]表示i到j个数的回文子序列的个数.f[i][j]可以从f[i][j-1]转移得到,就是看第j个数和[i,j-1]中的数形成了多少个新的回文子序列.因为回文子序列的两端都是相同的字母，所以可以先预处理出两个数组：pre,last分别表示i这个位置之前的a[i]最后一次出现的位置和之后第一次出现的位置.设k为i以后a[j]第一次出现的位置,p为j以前a[j]最后一次出现的位置,为了使得首位字母一样，f[i][j] += f[k + 1][j - 1],k,j两个端点的先不算.但是这样的话之前加了f[i][j-1]又会加多，所以减去多的部分f[k + 1][p - 1],因为a[j]作为末尾，开头一定要是a[j],最后对端点进行讨论，看k和j能组成几种回文子序列.
我个人认为j,k,p实际上就是固定的左右端点，用左右端点的方案乘左右端点里的方案就是这一个区间的方案数.好比f[i][j]减掉f[k+1][p-1],其实就是固定了左端点为k或p,右端点为j,看[k+1,p-1]里有多少种方案，乘上左右端点组合的方案(1),就是重复的部分.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int mod = 1e9 + 7; int T, n, m, k, f[6010][6010], last[6010], nextt[1010], a[6010], pre[6010]; int main() { scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &m, &k); memset(last, 0, sizeof(last)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); pre[i] = last[a[i]]; last[a[i]] = i; } memset(last, 0, sizeof(last)); for (int i = n; i >= 1; i--) { last[a[i]] = i; for (int j = i; j <= n; j++) { int k = last[a[j]], p = pre[j]; int temp = (p < k && k <= j) + (p <= k && k < j); f[i][j] = (f[i][j - 1] - f[k + 1][p - 1] + f[k + 1][j - 1] + temp) % mod; if (f[i][j] < 0) f[i][j] += mod; } } for (int i = 1; i <= m; i++) { int l, r; scanf("%d%d", &l, &r); printf("%d\n", f[l][r]); } } return 0; }
原文：http://www.cnblogs.com/zbtrs/p/7747779.html