Posted on 2011-12-03 13:09
C小加 閱讀(1605)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告
NYOJ地址：http://acm.nyist.net/JudgeOnline/problem.php?pid=271
題意：
給出一個區間，求區間內每一個數按規則（奇數取3n+1，偶數取n/2）變換最后變成1的步數，求最大的一個步數。
思路：
這道題在poj上很快就是水過了，用的是一般的笨方法，后來看到學校的oj也有這道題，就復制粘貼過去，結果WA了，好詭異。然后改了一些細節，TLE了，頓時無語。然后經過各種優化啊，記憶優化啊，有木有！！優化到不能再優化啊，還是TLE啊。沒辦法了，只能試試其他的方法了。很簡單就能想到打表，把題目要求的數據范圍內所有的步數都求出來，然后就可以順利的水了，水過后看見別人做的，用記憶的過了啊，有木有！！我怎么就沒過呢~~更多的還是打表~~我的時間有點慢，不解釋。。。。順便說一下，這道題還是很陰險的，做的時候要細心呀。。。
代碼：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int d[10003];
int main()
{
//freopen("input.txt","r",stdin);
int i,j,t;
memset(d,0,sizeof(d));
for(int k=2;k<10003;k++)//打表
{
t=k;
while(1!=t)
{
if(t&1)
{
t=t*3+1;
}
else t>>=1;
d[k]++;
}
}
while(cin>>i>>j)
{
int max=0,t=0;
cout<<i<<" "<<j<<" ";
if(i>j)
{
i^=j;j^=i;i^=j;
}
for(int k=i;k<=j;k++)
{
if(max<d[k])
max=d[k];
}
cout<<max+1<<endl;
}
return 0;
}