USACO Section 4.3 Buy Low, Buy Lower - DP+大数加法

这题的本体就是经典的最长非降子序列...第一问就是O(n^2)的最长降序列了...

而第二问则有技巧..首先明确的是要得到方案数..那么在dp更新最长长度时方案数要跟着传递更新..如果没有题目中所给的位置不同但序列每个数相等的序列只能算一个序列的条件...那么更新方案数是当dp更新长度时如果能更新得更长,那么就将方案数直接赋值过来..若相等则相加..

但是题目中又给出了这个条件...那么就用一个数组来记录那个数出现的最后位置...比如

3 2 1 3 2 1 6 5

前面三位可以得到最长的是3位为3 2 1方案数只有1种...继续往后扫..比如到了第6位..也是1..为了避免出现第1位,第2位,第6位组成重复的3位...那么新的数列中至少有一位是在两个1之间的..也就是第3位与第2位之间...但是这里也要注意..有些位置是更新不到...如第4位,第5位..所以要记i录下只有当这一位更新过..后面才可以根据这一位更新..这也就是为什么第3位到第6位之间的4,5位不能是用来更新6的原因..就这个数列来说...最长的就是3位..最长的方案就是前面3位组成的一种..而4,5,6位都是属于无法更新的...7,8位组成的最长也只能有2...所以如果在扫描时把出现的数的最后位置记录..就能每次只在最末尾两两相同的中间数用来更新...这样就不可能存在重复的队列了..

最后注意的是得到的方案数非常巨大...只能由大数来存储...方案数进行相加时也只能是大数加法...

Program:

/*  
ID: zzyzzy12   
LANG: C++   
TASK: buylow
*/      
#include<iostream>      
#include<istream>  
#include<stdio.h>      
#include<string.h>      
#include<math.h>      
#include<stack>
#include<map>
#include<algorithm>      
#include<queue>   
#define oo 1000000000  
#define ll long long  
#define pi (atan(2)+atan(0.5))*2 
using namespace std;  
struct node
{
      int w;
      int t[104];   
}dp[5005];
int i,j,n,a[5005],x,h[100000];
bool f[5005];
int main()  
{  
      freopen("buylow.in","r",stdin);   
      freopen("buylow.out","w",stdout);    
      memset(h,0,sizeof(h));
      memset(f,false,sizeof(f));
      cin>>n;
      for (i=1;i<=n;i++) 
      {
            cin>>a[i]; 
            dp[i].w=1; 
            memset(dp[i].t,0,sizeof(dp[i].t));
            dp[i].t[1]=1;
      }
      n++;  a[n]=0;  dp[n].w=1;  
      for (i=1;i<=n;i++)
      {
            if (!h[a[i]]) f[i]=true;
            j=h[a[i]]+1; 
            h[a[i]]=i; 
            for (;j<i;j++)
              if (f[j] && a[j]>a[i])
                if (dp[j].w+1>dp[i].w)
                {
                     dp[i].w=dp[j].w+1;
                     for (x=0;x<=100;x++) dp[i].t[x]=dp[j].t[x]; 
                     f[i]=true;                
                }else
                if (dp[j].w+1==dp[i].w) 
                {
                     for (x=0;x<=100;x++)
                     {
                           dp[i].t[x]+=dp[j].t[x];  
                           if (dp[i].t[x]>9) 
                           {
                                 dp[i].t[x+1]+=dp[i].t[x]/10;
                                 dp[i].t[x]%=10;                   
                           }
                     }             
                }
      }
      cout<<dp[n].w-1<<" ";
      for (i=100;i>0;i--) 
         if (dp[n].t[i]) break;
      for (;i>0;i--) cout<<dp[n].t[i];
      cout<<endl;
      return 0;     
}