Algorithm
Algorithm

DP（SJTU OJ 1012）

Description

有一个数列，它是由自然数组成的，并且严格单调上升。最小的数不小于S，最大的不超过T。现在知道这个数列有一个性质：后一个数相对于前一个数的增长率总是百分比下的整数（如5相对于4的增长率是25%，25为整数；而9对7就不行了）。现在问：这个数列最长可以有多长？满足最长要求的数列有多少个？

Input Format

输入仅有一行，包含S和T两个数（ 0<S<T≤200000）。

30%的数据，0<S<T≤100；

100%的数据，0<S<T≤200000。

Output Format

输出有2行。第一行包含一个数表示长度，第二行包含一个数表示个数。

Sample Input

2 10

Sample Output

5
2

样例解释

2 4 5 6 9以及2 4 5 8 10

解题思路

DP动态规划求解

如何将从S到T的问题转变成从S到T-1的问题呢？

首先求出从S到T-1的最长序列有几个，他的末端分别是谁，然后把T和末端数字进行比较，看是否可以延续这个最长序列，从而决定是否要增加序列的长度。

DP设定以下几个状态 * d[i] 表示以i为结尾的最长序列的长度 * times[i] 以i为结尾的最长序列的个数 * cnt[x] 长度为x的序列的个数

算法：

从S到T遍历起点i。

逆向思考：假设增长的百分率为j%，也就是题目中的25。则确定序列中的下个数字tmp 与i的关系为

\((tmp - i)/i = j/100\) 整理得 \(tmp = i + i*j/100\) 注意这里的 \(tmp<=T\)。

得到上述关系后，DP的状态转移为：

首先，我们的tmp是在以i为结尾的序列后加入的，长度为d[i]+1, 因此以tmp的结尾的序列长度和次数要更新；

如果d[tmp] 和 d[i]+1相等，那么在此之前以tmp结尾的序列最长长度和之前的序列长度一致。也就是说 \(times[tmp] += times[i]\)。

如果d[tmp] < d[i]+1, 说明新的序列比原来的还要长，所以\(d[tmp] = d[i]+1, times[tmp] = times[i]\)。

更新总的最大长度\(ans = max（ans,d[tmp]）\);

最后输出ans和cnt[ans]


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;

const int maxn=200007;
int d[maxn];
ll cnt[maxn],times[maxn];
//cnt[i]存储的是 长度为i的序列的个数
//d[i]存储的是以i结尾的序列最长的长度
int main()
{
    int s,t;
    cin>>s>>t;
    memset(cnt,0,sizeof(cnt));
    int i,j,tmp,ans=1;
    cnt[1]=t-s+1;

    for(i=s;i<=t;i++)
        d[i]=times[i]=1; //初始化为1

    for(i=s;i<=t;i++) //遍历每个数作为起点
        for(j=1;j<=100;j++)    if( (i*j)%100 == 0) //假设增长率为j%
        {
            //则在此增长率下 得到的数为 tmp 可以看出,要让tmp为整数 必须i*j是100的倍数
            tmp = i + i*j/100;
            if( tmp <= t ) //如果这个tmp是在规定范围内的 我们就找到了一个解
            {
                if(d[i]+1 > d[tmp]) //这时要比较 看看要不要更新以tmp结尾的最长的长度
                {
                    d[tmp] = d[i] + 1;//以tmp为结尾的序列的长度 为 以i为结尾的序列的长度 再加上1 表示算上tmp
                    times[tmp] = times[i]; //发生了最长长度的更新 所以要重置 以tmp结尾的最长长度的重复次数为 i的
                }
                else if(d[i]+1==d[tmp]) //恰好是重复的最长长度 
                {
                    times[tmp] += times[i];//则最长长度的次数 增加 以i结尾的最长长度重复次数
                }

                ans = max(ans,d[tmp]);  //更新ans
                //d[i]+1 表示以i结尾的序列长度+tmp所增加的1位 这个长度的子列数量要增加times[i]
                cnt[d[i]+1] += times[i];
            }
        }
    cout<<ans<<cnt[ans];
    return 0;
}