usaco_4_3_1_buylow-最长不下降子序列的个数.cpp

usaco自己做的1到5章的代码

/*
PROB: buylow
LANG: C++
*/
/*
这道题很有意思，乍一看，它就是最长下降子序列，第一个问题确实是这样，对于5000的规模我们很容易给出O(NlogN)的算法。
不过这道题目的第二问是要得出最长序列的个数，而且序列相同位置不同的都只能算一个。不知道各位大牛有没有NLgN的算法，反正我是想不出了……
那么都用N^2的动归算法吧，第一个问题：
ls[i]=max{ ls[j] | 0 <= j < i ,p[j]>p[i] }+1;
其中，ls[i]为第i个数字为结尾的序列中最长下降子序列的长度，p[i]为输入的第i天的股价。

考虑第二问，如果不牵扯重复的问题，那么递推式容易给出，如下：
countt[i]=sum{ countt[j] | 0 <= j < i ,p[j]>p[i] , ls[i]==ls[j]+1};
这其实是加法原则的应用，要得到第i个长度为m的序列有多少种，只需计算0 ~ i-1中所有价格高于i的，并别长度为m-1的序列个数之和！

  在处理去重复问题时，我借鉴了某大牛的一种方法：
  建立数组next[MAXV]，对于序列中任意元素i，next[i]的值为i ~ n-1中的第一个价格等于p[i]的位置。如果没有，就为0
  这样，我们在处理countt相加时，对于每一个j，只需保证next[j]==0 || next[j]>i就可以，意思就是在当前j ~ i-1的区间中没有价格等于j的元素了，这样，总是处理区间中重复元素的最后一个！
  
最后要特别注意，countt的值会非常大，所以相加时必须用高精度加法！
*/
#include<iostream>
#include<fstream>
#include<algorithm>
#define MAXV 5002
#define cin fin
using namespace std;
ifstream fin("buylow.in");
ofstream fout("buylow.out");
int p[MAXV];
int ls[MAXV];
int next[MAXV];
char countt[MAXV][1001];
int top,m,n;
char sum[1001];
inline int maxf(int a,int b)
{
    return a>b?a:b;
}
void pluschar(char *a,char *b)
{
    int length,pl,i;
    length=maxf(a[1000],b[1000]);
	a[1000]=length;
    i=0;pl=0;
    while(length>0)
    {
        pl=(a[i]-'0')+(b[i]-'0')+pl;
        a[i]=pl%10+'0';
        pl/=10;
        i++;
        length--;
    }
    if(pl>0) {a[i]='1'; a[1000]++;}
}
void writes(char *s)
{
	int i;
	for(i=s[1000]-1;i>=0;i--) fout<<s[i];
	fout<<endl;
}
int main()
{
    int i,j,k,maxt;
    memset(countt,'0',sizeof(countt));
    memset(sum,'0',sizeof(sum));
    cin>>n;
    for(i=0;i<=n;i++) countt[i][1000]=0;
    sum[1000]=0;
    for(i=0;i<n;i++) cin>>p[i];
    for(i=0;i<n;i++)
        for(next[i]=0,j=i+1;j<n;j++)
        if(p[i]==p[j]) {next[i]=j; break;}
    ls[0]=1;
    for(i=1;i<n;i++)
    {
        for(j=0,maxt=0;j<i;j++)
        {
            if(p[j]>p[i] && ls[j]>maxt) maxt=ls[j];
        }
        ls[i]=maxt+1;
    }
    for(i=0,maxt=0;i<n;i++) if(ls[i]>maxt) maxt=ls[i];
    fout<<maxt<<' ';
	ls[n]=maxt+1;
    for(i=0;i<=n;i++)
    {
		//if(next[i]!=0 && ls[i]==ls[next[i]]) continue;
        if(ls[i]==1)
        {
            countt[i][0]='1';
            countt[i][1000]=1;
            continue;
        }
        for(j=0;j<i;j++)
        {
            if(p[j]>p[i] && ls[i]==ls[j]+1 && (next[j]==0 || next[j]>i))
                pluschar(countt[i],countt[j]);
        }

    }
    writes(countt[n]);
    return 0;
}