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;
}