ZOJ 2702 UNRHYMABLE RHYMES（DP）

题目：给定一首带有许多数字的诗，例如“AABB”、“ABAB”、“ABBA”和“AAAA”诗句押韵。从它们中选择，找出可以形成的押韵句子的最大数量，并输出这些句子在原始序列中的位置。

样本输入

15
1 2 3 1 2 1 2 3 3 2 1 1 3 2 2

3
1 2 3
样本输出

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次

路径打印类真的很乱

代码显示如下：

????

1 # 包括<iostream>
2 # 包括<cstdio>
3 # 包含<向量>
4 # 包含<算法>
5 使用命名空间标准；
6 常量整数 N = 4005;
7 int 数据[N],ks[N];
8 整数 n,kn;
9 int dp[N];
10 向量<int> 路径[N]; //记录路径
11 向量<int> pos[N];
12 int par[N]; //路径压缩
13 int out[N/4]; //输出路径
14
15 无效解决（）
16 {
17 如果（n < 4）
18 {
19 printf("0\n\n");
20返回；
二十一     }
22kn = n;
23 排序(ks,ks+kn); //原始序列被复制并排序
24 kn = 唯一（ks,ks+kn） - ks； //去重函数，返回相邻不重复的个数，即元素类型个数
25 整数 i,j,k;
26 for(i=0;i<n;i++)
27 {
28 数据[i] = lower_bound(ks,ks+kn,data[i]) - ks;
29 //lower_bound() 返回一个迭代器，它指向第一个可以在不破坏容器顺序的情况下将 value 插入到由 [first, last) 标记的有序序列中的位置，并且该位置标记了一个大于或等于 value 的值。
30 }
31 for(i=0;i<=3;i++)
32 {
33 dp[i] = 0；
34 标准杆 [i] = -1；
35 }
36 向量<int>tmp;
37 for(i=3;i<n;i++)
38 {
39 dp[i+1] = dp[i];
40 路径[i+1] = 路径[i];
41 标准杆[i+1] = 标准杆[i];
42 for(j=0;j<kn;j++)
43 位置[j].clear();
44 tmp.clear();
45 for(j=i;j>=0;j--)
46 {
47 k = 数据[j]；
48 pos[k].push_back(j+1);
49 if(pos[k].size()==2)
50 {
51 tmp.push_back(pos[k][0]);
52 tmp.push_back(pos[k][1]);
53 位置[k].clear();
54 if(tmp.size()==4) 中断；
55 }
56 }
57 如果（j >= 0）
58 {
59 如果（dp[i+1] < dp[j]+1）
60 {
61 dp[i+1] = dp[j] + 1；
62排序（tmp.begin（），tmp.end（））；
63 路径[i+1] = tmp; //同样是向量类型，可以赋值
64 par[i+1] = j;
65 }
66 }
67 }
68 printf("%d\n",dp[n]);
69 诠释你;
70u = n;
71 for(i=dp[n]-1;i>=0;i--)
72 {
73 出[i] = 你;
74 u=par[u];
75 }
76 for(i=0;i<dp[n];i++)
77 {
78 为（j=0；j<3；j++）
79 {
80 printf("%d",path[out[i]][j]);
81 }
82 printf("%d\n",path[out[i]][j]);
83 }
84 把（“”）；
85 }
86
87 int main()
88 {
89 while(scanf("%d",&n)!=EOF)
90 {
91 for(int i =0; i<n; i++)
92 {
93 scanf("%d",&data[i]);
94 ks[i] = 数据[i];
95}
96 解决（）；
97}
98 返回 0；
99 }

(Title: give a poem with many numbers, such as the rhyme of "AABB", "ABAB", "Abba" and "AAAA". Select from them, find out the maximum number of rhyming sentences that can be formed, and output the position of these sentences in the original sequence.
Sample input
fifteen
1 2 3 1 2 1 2 3 3 2 1 1 3 2 2
three
1 2 3
Sample output
three
1 2 4 5
7 8 9 10
11 12 14 15
0
Analysis: let DP [i] represent the maximum number of rhyming sentences from 1 to I, and f (I, J) represent 1 when rhyming sentences can be formed between [I, J], otherwise it is 0
Then DP [i] = max {DP [I-1], DP [J] + F (j + 1, I)}
When the number of occurrences of two numbers between (I, J) is greater than or equal to 2, f (I, J) = 1, the two numbers can be equal, that is, one number occurs 4 times
The path printing class is really messy
The code is shown as follows:
????
1 # including < iostream >
2 # including < cstdio >
3 # contains < vector >
4 # contains < algorithm >
5. Use namespace standards;
6 constant integer n = 4005;
7 int data [n], KS [n];
8 integer n, kn;
9 int dp[N];
10 vector < int > path [n]// Record path
11 vector < int > POS [n];
12 int par[N]; // Path compression
13 int out[N/4]; // Output path
fourteen
15 invalid resolution ()
16 {
17 if (n < 4)
18 {
19 printf("0\n\n");
20 return;
Twenty one}
22kn = n;
23 sorting (KS, KS + KN)// The original sequence is copied and sorted
24 kn = unique (KS, KS + KN) - KS// The de duplication function returns the number of adjacent non duplicates, that is, the number of element types
25 integer I, J, K;
26 for(i=0;i<n;i++)
27 {
28 data [i] = lower_ bound(ks,ks+kn,data[i]) - ks;
29 //lower_ Bound () returns an iterator that points to the first position where value can be inserted into an ordered sequence marked by [first, last] without breaking the container order, and the position marks a value greater than or equal to value.
30 }
31 for(i=0;i<=3;i++)
32 {
33 dp[i] = 0；
34 standard bar [i] = - 1;
35 }
36 vector < int > TMP;
37 for(i=3;i<n;i++)
38 {
39 dp[i+1] = dp[i];
40 path [i + 1] = path [i];
41 standard bar [i + 1] = standard bar [i];
42 for(j=0;j<kn;j++)
43 position [J] clear();
44 tmp. clear();
45 for(j=i;j>=0;j--)
46 {
47 k = data [J];
48 pos[k]. push_ back(j+1);
49 if(pos[k].size()==2)
50 {
51 tmp. push_ back(pos[k][0]);
52 tmp. push_ back(pos[k][1]);
53 position [k] clear();
54 If (TMP. Size() = = 4) interrupt;
55 }
56 }
57 If (J > = 0)
58 {
59 If (DP [i + 1] < DP [J] + 1)
60 {
61 dp[i+1] = dp[j] + 1；
62 sort (TMP. Begin()) end（））；
63 path [i + 1] = TMP// It is also a vector type and can be assigned
64 par[i+1] = j;
65 }
66 }
67 }
68 printf("%d\n",dp[n]);
69 interpret you;
70u = n;
71 for(i=dp[n]-1;i>=0;i--)
72 {
73 out [i] = you;
74 u=par[u];
75 }
76 for(i=0;i<dp[n];i++)
77 {
78 is (J = 0; J < 3; j + +)
79 {
80 printf("%d",path[out[i]][j]);
81 }
82 printf("%d\n",path[out[i]][j]);
83 }
84 ("");
85 }
eighty-six
87 int main()
88 {
89 while(scanf("%d",&n)!= EOF)
90 {
91 for(int i =0; i<n; i++)
92 {
93 scanf("%d",&data[i]);
94 KS [i] = data [i];
95}
96 solution ();
97}
98 returns 0;
99 }
)