题目链接:
题目大意:给定有很多数字组成的诗,譬如 “AABB”, “ABAB”, “ABBA” and “AAAA”形式的诗句是押韵的。从中挑选,求最多可以构成多少押韵句,并且输出这些句子在原序列中的位置。
Sample Input
151 2 3 1 2 1 2 3 3 2 1 1 3 2 231 2 3
Sample Output
31 2 4 57 8 9 1011 12 14 150
分析:设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次
路径打印课真是乱啊
代码如下:
1 # include2 # include 3 # include 4 # include 5 using namespace std; 6 const int N = 4005; 7 int data[N],ks[N]; 8 int n,kn; 9 int dp[N];10 vector path[N]; //记录路径11 vector pos[N];12 int par[N]; //路径压缩13 int out[N/4]; //输出路径14 15 void solve()16 {17 if(n < 4)18 {19 printf("0\n\n");20 return ;21 }22 kn = n;23 sort(ks,ks+kn); //原序列复制后排序24 kn = unique(ks,ks+kn) - ks; //去重函数,返回相邻不重复的个数,即元素种类数25 int i,j,k;26 for(i=0; i