子序列 题解
子序列
https://ac.nowcoder.com/acm/problem/17065
萌新一枚 多多指教！
第一眼看到这个题感觉有些像最长升序子序列一样。
后来发现也是差不多这样做。
对数学敏感点的朋友们会发现如果xab<xba,并且xbc<xcb，我们就可以推出xac<xca，这无非是高中最常用的两边开根号做比较的题目吧。
发现这一点的话基本也就好做了。我们就dp走起。
类似于最长升序子序列的解法一样。
我们可以推出状态转移方程dp[i] =1+ 
i-1k=1 dp[k](符合可以插入的k);
1(是因为本身也算是一个子序列)
如果我们check(k,i)符合我们上面说的条件xki<xik,我们就可以加上dp[k]，这就用到上面推出那三个相关的式子的原理。
之后就非常容易了，就直接把dp数组求和输出就得了。记得%mod取余。
import java.util.*;
import java.math.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
public class Main {
public static void main(String args[])throws IOException
{
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int n = (int)in.nval;
int s[] = new int[n+1];
long dp[] = new long[n+1];
long mod = 1000000007,sum,max=0;
for(int i=1;i<=n;i++)
{
in.nextToken();
s[i] = (int)in.nval;
}
for(int i=1;i<=n;i++)
{
sum=1;
for(int k=1;k<i;k++)
{
if(check(k,i,s))
sum+=dp[k];
}
dp[i] +=sum%mod;
max+=dp[i];
}
out.print(max%mod);
out.flush();
}
public static boolean check(int a,int b,int s[])
{
if(b*Math.log(s[a])<a*Math.log(s[b]))
return true;
else
return false;
}
}
网易公司福利 161人发布
