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
52
样例解释
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
接下来有两条路可以走: 正向思考 我们可以遍历从i+1到T的每一个数去和i进行比较，判断是否满足条件，但是这样肯定会超时，因为数据量太大。
另外一个想法就是逆向思维，我们最终的判断是需要找到增长率的百分比为整数的那个数。
假设百分下整数为j，则确定的那个数 tmp 与 i的关系为
(tmp-i) / i = j / 100 整理可以得到 tmp = i + i*j/100 (可以看出 tmp为整数的条件要求 i*j%100==0)
得到了这个tmp（必须小于等于T）之后，开始进行DP状态转移
状态转移关系如下：
首先，我们的tmp是在以i为结尾序列之后添加的，长度为d[i]+1， 以tmp的结尾的最长的序列长度和次数可能要更新
如果d[tmp]和d[i]+1相等, 说明在此之前 以tmp结尾的序列的最长长度 和 刚刚得到的序列长度一致
所以要将 times[tmp] += times[i] //在这个序列的d[i]部分的重复度为times[i] ( >=1 )
如果d[tmp]<d[i]+1，说明新的序列长度比原来的还要长，所以不仅要更新最长长度d[tmp] 还要更新 最长长度的重复次数times[tmp]
d[tmp] = d[i] + 1
times[tmp] = times[i]
之后，我们要更新总的最大长度ans : ans = max(ans,d[tmp])
更新当前序列所占长度的序列数 cnt[d[i]+1] += tims[i] * 1; (*1是为了更好的说明 times[i]的是d[i]部分的重复度 1表示tmp的重复度 , 和1285里的一个部分很像)
至此状态转移结束
最后只需输出 ans 和 cnt[ans]即可
PS:说明一点，就是为什么j从1到100即可。 增长率从1%到100%的覆盖区间恰好是，i到2i这个部分。
那么为什么是2i不是3i呢。可以举个例子，比如序列x,x,x,x,x,i,x,x,x,3i的长度一定没有x,x,x,x,x,i,x,,2i,x,x,3i 的长度长，所以考虑最优解只要在i到2i里找下一位即可。
当然，更严谨的数学证明会比较麻烦，需要证明在2i之后的每一个能够满足条件的tmp都可以从i,tmp 可以转换至少为 i,x,tmp的结构 其中x小于2i。 有空再证明吧，反正AC了。。
代码如下:
#include#include #include #include 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< <