大家知道，黄药师不仅武功高超，而且酷爱音乐和诗歌。看到桃花岛来了个新客人，而且不是靠真武功进来的，就准备为难为难你。
他写了一首N行诗句的诗歌，美中不足的是这些诗句并不押韵，黄药师非常想遵循古诗的押韵。诗歌被分为若干段，每段都是四行诗。每一句诗都有一个韵脚，假如A和B表示两种不同的韵脚，每段四行诗的韵脚只可能是“AABB”，“ABAB”，“ABBA”和“AAAA”中的一种。
黄药师将诗句的韵脚都编了号，具有相同编号的句子代表有相同的韵脚。现在，黄药师想删掉一些句子，使得剩下的都是遵循押韵规则的四行诗，而且不允许改变诗句的顺序。
现在就问你：如何找出满足条件最长的诗歌？
第一行为一个整数N（1≤N≤4000），代表黄药师写的诗歌的句子数。
第二行为N个整数，分别表示每一行诗的韵脚，这些数字都是不超过109109的正数，每个数之间用1个空格隔开。
一行，一个整数k，为黄药师最多能够得到的四行诗个数。
15
1 2 3 1 2 1 2 3 3 2 1 1 3 2 2
3
我们设$c[i]$为$[1,i]$中$i$与最后一个诗句的长度，则如果$c[i - 1] \geqslant 3$，那我们就暴力判断是否能形成诗句，注意这里只用判断$3$个位置，第$4$个位置由$i$充当就好了，这样可以减少很多时间。
#include <iostream> #include <algorithm> #define MAX_N (4000 + 5) using namespace std; int n; int a[MAX_N]; int dp[MAX_N], c[MAX_N]; bool Judge(int x, int lt, int rt) { for(register int i = lt; i + 2 <= rt; ++i) { if(a[i] == x) for(register int j = i + 1; j + 1 <= rt; ++j) { for(register int k = j + 1; k <= rt; ++k) { if(a[j] == a[k]) return true; } } else for(register int j = i + 1; j + 1 <= rt; ++j) { if(a[i] == a[j]) for(register int k = j + 1; k <= rt; ++k) { if(a[k] == x) return true; } else if(a[j] == x) for(register int k = j + 1; k <= rt; ++k) { if(a[i] == a[k]) return true; } } } return false; } int main() { cin >> n; for(register int i = 1; i <= n; ++i) { cin >> a[i]; } for(register int i = 1; i <= n; ++i) { if(c[i - 1] >= 3 && Judge(a[i], i - c[i - 1], i - 1)) { dp[i] = dp[i - 1] + 1; c[i] = 0; } else { dp[i] = dp[i - 1]; c[i] = c[i - 1] + 1; } } cout << dp[n]; return 0; }
原文：https://www.cnblogs.com/kcn999/p/10806039.html
