题目地址:

http://codeforces.com/gym/100211/attachments/download/1726/20032004-lyetniye-pyetrozavodskiye-sbory-andrew-stankevich-contest-9-en.pdf

题目大意:

有n个数,你需要找出尽多组互不相交的形如"AAAA""AABB""ABAB""ABBA"之一的子序列

n<=4000

样例解释(我知道这个题目大意我一定过一段时间就看不懂了)

1 2 4 5分别对应了"1 2 1 2",符合"ABAB"的形式

7 8 9 10分别对应了"2 3 3 2",符合"ABBA"的形式

11 12 14 15分别对应了"1 1 2 2",符合"AABB"的形式

大概你也能看的出来,没有啥别的办法分了

做法:dp

dp[i]表示前i个里面最多能凑几组

程序中,c[i][j]表示了第j个能否转移到i

(如果是-1则代表了是AAAA转移法,0则是不能转移,否则记录了第一个B的位置)

那么提前暴力出每个转移即可

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
map<int,int> ma;
int a[5005];
vector<int> b[5005];
int c[4005][4005];
int dp[4005];
int last[4005];
void dfs(int x)
{
    if (x==-1)
    {
        return;
    }
    if (x==0)
    {
        return;
    }
    dfs(last[x]);
    if (dp[last[x]]+1==dp[x])
    {
        if (c[x][last[x]]==-1)
        {
            vector<int>::iterator t=lower_bound(b[a[x-1]].begin(),b[a[x-1]].end(),last[x]);
            printf("%d ",(*t)+1);
            t++;
            printf("%d ",(*t)+1);
            t++;
            printf("%d ",(*t)+1);
            t++;
            printf("%d\n",(*t)+1);
        }
        else
        {
            int t=c[x][last[x]]-1;
            vector<int>::iterator t1=lower_bound(b[a[x-1]].begin(),b[a[x-1]].end(),x-1);
            vector<int>::iterator t2=lower_bound(b[a[t]].begin(),b[a[t]].end(),t);
            static int a[5];
            a[0]=(*t1)+1;
            t1--;
            a[1]=(*t1)+1;
            a[2]=(*t2)+1;
            t2++;
            a[3]=(*t2)+1;
            sort(a,a+4);
            printf("%d %d %d %d\n",a[0],a[1],a[2],a[3]);
        }
    }
}
int main()
{
    freopen("rhymes.in","r",stdin);
    freopen("rhymes.out","w",stdout);
    int n;
    scanf("%d",&n);
    int i;
    int sum=0;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        if (ma.find(a[i])==ma.end())
        {
            ma[a[i]]=sum++;
        }
        a[i]=ma[a[i]];
        b[a[i]].push_back(i);
    }
    for (i=0;i<sum;i++)
    {
        int j;
        for (j=i+1;j<sum;j++)
        {
            int k,l;
            for (k=1;k<b[i].size();k++)
            {
                for (l=1;l<b[j].size();l++)
                {
                    if (b[i][k]>b[j][l])
                    {
                        c[b[i][k]+1][min(b[i][k-1],b[j][l-1])]=1+b[j][l-1];
                    }
                    else
                    {
                        c[b[j][l]+1][min(b[i][k-1],b[j][l-1])]=1+b[i][k-1];
                    }
                }
            }
        }
    }
    for (i=0;i<sum;i++)
    {
        int j;
        for (j=3;j<b[i].size();j++)
        {
            c[b[i][j]+1][b[i][j-3]]=-1;
        }
    }
    for (i=0;i<=n;i++)
    {
        dp[i]=0;
        if (i!=0) dp[i]=dp[i-1];
        last[i]=i-1;
        int j;
        for (j=0;j<i;j++)
        {
            if (c[i][j])
            {
                if (dp[j]+1>dp[i])
                {
                    dp[i]=dp[j]+1;
                    last[i]=j;
                }
            }
        }
    }
    printf("%d\n",dp[n]);
    dfs(n);
    return 0;
}