http://hi.baidu.com/huicpc0207/item/f11a06f36ecfe91484d278fddisscus里說有比O(n)還低的DP方法，之前我也構(gòu)造出來了，不過是不正確的。比O(n)低的DP方法？？？
問了問院長老師，希望她能給個(gè)比較好的算法哦哦哦
歸納、構(gòu)造數(shù)列：根據(jù)k=1,k=2找到思路，找出必?cái)B(tài)即可。
總結(jié)：
1、多研究思考些有難度的數(shù)學(xué)問題，自己找到辦法。
2、復(fù)雜問題總是有簡單辦法的。
3、難題代碼實(shí)現(xiàn)一般很容易！
#include<stdio.h>
#include<string.h>
#include<math.h>
int a[1000005],r[1000005];
int solve(int n,int k)
{
int i,j,ans;
a[0]=0;r[0]=0;
for (i=1,j=0;i<=1000000;i++)
{
a[i]=r[i-1]+1;
while (j+1<i && a[j+1]*k <a[i])
j++;
r[i]=a[i]+r[j];
if (r[i]>=n)
break;
}
if (a[i]==n)
return 0;
while (i>=1)
{
if (n==a[i])
return a[i];
else
if (n>a[i])
n-=a[i];
i--;
}
return ans;
}
int main()
{
int t,cas=0,n,k,ans;
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&k);
ans=solve(n,k);
printf("Case %d: ",++cas);
if (!ans)
printf("lose\n");
else
printf("%d\n",ans);
}
return 0;
}