1012. 增長(zhǎng)率問題
Description
有一個(gè)數(shù)列，它是由自然數(shù)組成的露泊，并且嚴(yán)格單調(diào)上升掌测。最小的數(shù)不小于S，最大的不超過T∑芤桑現(xiàn)在知道這個(gè)數(shù)列有一個(gè)性質(zhì)：后一個(gè)數(shù)相對(duì)于前一個(gè)數(shù)的增長(zhǎng)率總是百分比下的整數(shù)（如5相對(duì)于4的增長(zhǎng)率是25%讨永，25為整數(shù)；而9對(duì)7就不行了）∮龈铮現(xiàn)在問：這個(gè)數(shù)列最長(zhǎng)可以有多長(zhǎng)卿闹？滿足最長(zhǎng)要求的數(shù)列有多少個(gè)揭糕？
Input Format
輸入僅有一行，包含S和T兩個(gè)數(shù)（ 0<S<T≤200000 ）锻霎。
30%的數(shù)據(jù)插佛，0<S<T≤100 ；
100%的數(shù)據(jù)量窘，0<S<T≤200000雇寇。
Output Format
輸出有2行。第一行包含一個(gè)數(shù)表示長(zhǎng)度蚌铜，第二行包含一個(gè)數(shù)表示個(gè)數(shù)锨侯。
Sample Input
2 10
Sample Output
5
2
樣例解釋
2 4 5 6 9以及2 4 5 8 10
分析
這道題使用動(dòng)態(tài)規(guī)劃分析，其關(guān)鍵在于：
(tmp-i)/i=j/100
展開則有：tmp=i+ij/100冬殃，即ij能被100整除囚痴。
#include <iostream>
using namespace std;
int main()
{
long long int max_length[200000], max_num[200000];
int s,t;
int i,j;
int tmp;
long long int maxl=1,maxn; //注意溢出，和最少一個(gè)
cin>>s>>t;
maxn=t-s+1; //當(dāng)為一個(gè)的時(shí)候审葬，其可以有這么多個(gè)深滚，考慮質(zhì)數(shù)情況
for(i=s; i<=t; i++)
max_length[i]=max_num[i]=1;
for(i=s; i<=t; i++) {
for(j=1; j<=100; j++){
if((i*j)%100 == 0) {
tmp=i+(i*j)/100;
if(tmp<=t) {
if(max_length[i]+1 > max_length[tmp]) {
max_length[tmp] = max_length[i]+1;
max_num[tmp]=max_num[i];
}
else if(max_length[i]+1==max_length[tmp])
max_num[tmp]+=max_num[i];
if(max_length[tmp]>maxl) {
maxl=max_length[tmp];
maxn=max_num[tmp];
}
else if(max_length[tmp]==maxl)
maxn+=max_num[i];
}
}
}
}
cout<<maxl<<endl<<maxn<<endl;
return 0;
}
