2016-09-29

HDU 5760 Palindrome Bo【dp】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5760

题意：

给定$n$个元素的序列，求最长的回文子序列长度及不同的个数，若两个序列中同一个位置的元素不同，则视为不同序列。
数据范围$1 \le n \le 5000$

分析：

官方题解中讲的很清晰。
先预处理出每个位置的$nxt$和$pre$数组，然后$l$逆序。
对于每个$l$用一个$tmp$来保存当前最优解及个数，$r$正序（保证当前处理的区间的子区间都已经处理过）扫一遍。
如果$a[l] = a[r]$，则为合法状态，更新$dp[l][r]$和$tmp$。
如果$a[l] \gt a[r]$，令$i=nxt[l][a[r]]$，将$dp[i][r]$与$tmp$进行比较并更新，若二者长度一样，那么就要处理重复部分，令$j=pre[r][a[r]]$，若$[i,j]$和$[i,r]$之间的回文串长度一样，而后者区间更长显然包含前者，答案个数更多，那么就要除去$[i,j]$的答案。

代码：


/*************************************************************************
    > File Name: 5760.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/29 20:42:46
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int>p;
const int maxn = 5e3 + 5, mod = 1e9 + 7;
p dp[maxn][maxn];
int a[maxn], na[maxn];
int nxt[maxn][maxn], pre[maxn][maxn];
int main (void)
{
	int n;
	//freopen("1009.in", "r", stdin);
	while(~scanf("%d", &n)){
		for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), na[i] = a[i];
		memset(nxt, -1, sizeof(nxt));
		memset(pre, -1, sizeof(pre));
		for(int i = 1; i <= n; ++i){
			dp[i][i] = p(1, 1);
			for(int j = i + 1; j <= n; ++j){
				dp[i][j] = p(0, 0);
			}
		}
		sort(na + 1, na + n + 1);
		int nn = unique(na + 1, na + n + 1) - (na + 1);
		for(int i = 1; i <= n; ++i){
			a[i] = lower_bound(na, na + nn, a[i]) - na;
		}
		for(int i = 0; i <= n + 1; ++i){
			for(int j = i + 1; j <= n; ++j){
				if(nxt[i][a[j]] == -1) nxt[i][a[j]] = j;
			}
			for(int j = i - 1; j >= 1; j--){
				if(pre[i][a[j]] == -1) pre[i][a[j]] = j;
			}
		}
		for(int i = n; i >= 1; --i){
			p tmp = p(0, 0);
			for(int j = i + 1; j <= n; ++j){
				if(a[i] == a[j]){
					if(tmp.first == 0) dp[i][j] = p(2, 1);
					else dp[i][j] = p(tmp.first + 2, tmp.second);
				}
				if(a[i] >= a[j]){
					int f = nxt[i][a[j]];
					if(dp[f][j].first > tmp.first) tmp = dp[f][j];
					else if(dp[f][j].first == tmp.first){
						(tmp.second += dp[f][j].second) %= mod;
						int q = pre[j][a[j]];
						if(q == -1) continue;
						if(dp[f][j].first == dp[f][q].first) tmp.second -= dp[f][q].second;
						if(tmp.second < 0) tmp.second += mod;
					}
				}
			}
		}
		p ans = p(0, 0);
		for(int i = 1; i <= nn; ++i){
			int aa = nxt[0][i];
			int bb = pre[n + 1][i];
			if(aa == -1 || bb == -1) continue;
			if(dp[aa][bb].first > ans.first) ans = dp[aa][bb];
			else if(dp[aa][bb].first == ans.first) (ans.second += dp[aa][bb].second) %= mod;
		}
		printf("%d %d\n", ans.first, ans.second);
	}
	return 0;
}