chunlvxiong的部落格
題目描述：
給出N(1≤N≤5000)個數，要求一個子序列是遞減的，求出這個子序列的最大長度s，和長度為s的子序列的個數（注意，如果兩個序列的數值一模一樣它們算同一種序列）。
思考&分析：
用a[i]表示第i個數。
第一問求s應該較好解決，使用DP求解，用dp[i]表示i作為子序列末尾的最大長度，則方程為：
dp[i]=max{dp[j]+1|1≤j<i且a[j]>a[i]}
然後ans1=max{dp[i]|1≤i≤n}，時間複雜度O(N^2)。
第二問如果沒有數值一樣算同一種序列的限制，也比較好解決，同樣使用DP求解，用f[i]表示i作為子序列末尾且該子序列長度最大的方案種數：
dp[i]==1：f[i]=1
dp[i]>1：f[i]=Σf[j](1≤j<i且a[j]>a[i]且dp[i]==dp[j]+1)
ans2=Σf[i](dp[i]==ans1)
問題在于所有數值一樣算同一種序列，怎麼避免這個問題呢？方法如下：
如果存在a[x]==a[y]且dp[x]==dp[y](y<x)，那麼f[i]=Σf[j]中j的範圍僅限于y+1..x-1，因為1..y-1中的方案末尾放a[j]或是a[i]都是一樣的，為了避免重複計算，我們将其歸于a[j]，進而a[i]計算範圍減少。
對于dp[i]==1的，如果沒有dp[j]==1(1≤j<i)且a[j]==a[i]的，那麼f[i]=1，否則f[i]=0。
仍然有ans2=Σf[i](dp[i]==ans1)。
然而USACO出這個題的核心不在這兒……而是：由于N=5000，第二問的答案可能非常大，需要使用高精度。
是以總的時間複雜度為O(N^2*高精度複雜度)-->N=5000時非常容易T，為了保險我壓了四位，在USACO上跑了0.266s。
貼代碼：
#include <bits/stdc++.h>
using namespace std;
int n,a[5005],dp[5005];
struct gjd{
int num[25];
int &operator [] (int p) { return num[p]; }
void clear(){
memset(num,0,sizeof(num));
}
void set(int x){
clear();
num[0]=0;
while (x){
num[++num[0]]=x%10;
x/=10;
}
if (!num[0]) num[0]=1;
}
gjd operator +(gjd &b){
gjd c; c.clear();
c[0]=max(num[0],b[0]);
for (int i=1;i<=c[0];i++){
c[i]+=num[i]+b[i];
c[i+1]+=c[i]/10000;
c[i]%=10000;
}
while (c[c[0]+1]>0) c[0]++;
return c;
}
void print(){
printf("%d",num[num[0]]);
for (int i=num[0]-1;i>=1;i--){
if (num[i]<1000) putchar('0');
if (num[i]<100) putchar('0');
if (num[i]<10) putchar('0');
printf("%d",num[i]);
}
puts("");
}
}num[5005],res;
int main(){
freopen("buylow.in","r",stdin);
freopen("buylow.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
int ans=0;
for (int i=1;i<=n;i++){
dp[i]=1;
for (int j=1;j<i;j++)
if (a[i]<a[j])
dp[i]=max(dp[i],dp[j]+1);
ans=max(ans,dp[i]);
}
printf("%d ",ans);
res.set(0);
for (int i=1;i<=n;i++){
if (dp[i]==1){
num[i].set(1);
for (int j=i-1;j>=1;j--)
if (a[i]==a[j] && dp[j]==1){
num[i].set(0);
break;
}
}
else{
num[i].set(0);
for (int j=i-1;j>=1;j--){
if (a[i]==a[j] && dp[i]==dp[j])
break;
if (a[i]<a[j] && dp[i]==dp[j]+1)
num[i]=num[i]+num[j];
}
}
if (dp[i]==ans)
res=res+num[i];
}
res.print();
return 0;
} 轉載于:https://www.cnblogs.com/chunlvxiong/p/7436214.html