每日一题4月24日 子序列 线性dp
子序列
https://ac.nowcoder.com/acm/problem/17065
我觉得我的数学需要回炉重造。。
题目大意:
给一个n个元素构成序列,从中选取子序列使得选取的子序列能够满足i<j,a[i]^j<a[j]<i。问一共有多少种子序列选择方案。n<=100,a[i]<=100
思路:
其实我一开始的就想当然的认为了如果i<j<k,若a[i]^j<a[j]^i,那么就会有a[i]^k<a[k]^i。
这样的话就可以用dp解决。
令dp[i]表示以i为起点往右的满足条件的子序列方案数。
那么对于i来说,我们可以枚举i右边的j,若满足a[i]^j<a[j]^i,那么我们有
f[i]=∑f[j]
关键是a[i]^j和a[j]^i的判断,如果直接算的话肯定会炸的。
然后我就卡在这里了。。。
参考了一下别人的思路,可以用除法,把两个做一次除法,然后转化成(a[i]/a[j])^i * x^(j-i)。
这样做其实对精度要求还蛮高的,不过居然过了。
更好的做法其实是对两边取对数。
log(a[i]^j)=j * log(a[i])
log(a[j]^i)=i * log(a[j])
这个可以预处理,然后直接dp就好了。
最后提一下,一开始的结论是正确的。看了推导以后就不证了
代码:
#include<bits/stdc++.h> using namespace std; int n; typedef long long ll; const ll mod=1000000007; bool c[102][102]; ll f[102]; double a[102]; double calc(double x,int y){ double ans=1; while(y){ if(y%2)ans=ans*x; x=x*x; y=y/2; } return ans; } int main() { int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i],f[i]=1; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ double x,y; x=a[i];y=a[j]; if(x>=y)continue; double tmp=calc(x/y,i); for(int k=1;k<=j-i;k++){ tmp*=x; } if(tmp<1)c[i][j]=true; } } for(int i=n-1;i>=1;i--){ for(int j=i+1;j<=n;j++){ if(c[i][j])f[i]+=f[j],f[i]%=mod; } } ll ans=0; for(int i=1;i<=n;i++)ans+=f[i],ans%=mod; cout<<ans<<endl; return 0; }