题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1702
题目大意：给定有很多数字组成的诗，譬如 “AABB”, “ABAB”, “ABBA” and “AAAA”形式的诗句是押韵的。从中挑选，求最多可以构成多少押韵句，并且输出这些句子在原序列中的位置。
Sample Input
15
1 2 3 1 2 1 2 3 3 2 1 1 3 2 2 3
1 2 3
Sample Output
3
1 2 4 5
7 8 9 10
11 12 14 15 0
分析：设dp[i]表示从 1 到 i 之间押韵句的最大数目，f(i,j)表示当[i,j]之间可以组出一句押韵句时为1，否则为0
则dp[i] = max{dp[i-1] , dp[j] + f(j+1,i)}
当(i,j)之间有2个数出现的次数大于等于2时，f(i,j)=1，这2个数可以相等，即1个数出现4次
路径打印课真是乱啊
代码如下：
# include<iostream>
# include<cstdio>
# include<vector>
# include<algorithm>
using namespace std;
const int N = ;
int data[N],ks[N];
int n,kn;
int dp[N];
vector<int> path[N]; //记录路径
vector<int> pos[N];
int par[N]; //路径压缩
int out[N/]; //输出路径 void solve()
{
if(n < )
{
printf("0\n\n");
return ;
}
kn = n;
sort(ks,ks+kn); //原序列复制后排序
kn = unique(ks,ks+kn) - ks; //去重函数，返回相邻不重复的个数，即元素种类数
int i,j,k;
for(i=; i<n; i++)
{
data[i] = lower_bound(ks,ks+kn,data[i]) - ks;
//lower_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了一个大于等于value 的值。
}
for(i=; i<=; i++)
{
dp[i] = ;
par[i] = -;
}
vector<int >tmp;
for(i=; i<n; i++)
{
dp[i+] = dp[i];
path[i+] = path[i];
par[i+] = par[i];
for(j=; j<kn; j++)
pos[j].clear();
tmp.clear();
for(j=i; j>=; j--)
{
k = data[j];
pos[k].push_back(j+);
if(pos[k].size()==)
{
tmp.push_back(pos[k][]);
tmp.push_back(pos[k][]);
pos[k].clear();
if(tmp.size()==) break;
}
}
if(j >= )
{
if(dp[i+] < dp[j]+)
{
dp[i+] = dp[j] + ;
sort(tmp.begin(),tmp.end());
path[i+] = tmp; //同为vector类型，可赋值
par[i+] = j;
}
}
}
printf("%d\n",dp[n]);
int u;
u =n;
for(i=dp[n]-; i>=; i--)
{
out[i] = u;
u= par[u];
}
for(i=; i<dp[n]; i++)
{
for(j=; j<; j++)
{
printf("%d ",path[out[i]][j]);
}
printf("%d\n",path[out[i]][j]);
}
puts("");
} int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i =; i<n; i++)
{
scanf("%d",&data[i]);
ks[i] = data[i];
}
solve();
}
return ;
}