prob

【問題描述】

浩浩和琳琳從小就在一個學校，關系非常好，他們經常在一起討論題目，一起玩游戲，一起聊天。浩浩的數學成績非常棒，立志當一名“千秋萬載”的數學家J。

琳琳遇到不會做的數學題目，都會來問浩浩，浩浩每次都會熱心的解決。可是就在昨天，琳琳問浩浩一道有關數列的題目，浩浩想了一整天，腦袋都想大了，還是沒有結果，立志成為大數學家的浩浩不想在琳琳面前丟丑，于是回家冥思苦想了一晚上，結果……

至于結果怎么樣了，還是大家自由想象吧，我們現在討論的是琳琳問的這道題目：

?

?

對于這樣一個奇怪的遞推關系：

現在給定正整數N,P，要求An，你會做嗎？

?

【輸入文件】

輸入只有兩個正整數N,P(N,P<1001)。

?

【輸出文件】

輸出只有一行，即An。

?

【樣例】

Prob.in 1 3 ?

Prob.out 1

這是一道好題。因為sqrt(p)可能是無理數，所以不能夠直接簡單遞推。

對ai進行手動迭代的時候，我們會發現任意的ai都可以表示成a(n-a*p-b*sqrt(p))的形式。

于是我們用f[i][j]表示a(n-i*p-j*sqrt(p))

f[i][j]的遞推很簡單

f[i][j] = f[i+1][j] + f[i][j+1] (n-i*p-j*sqrt(p) > p)

f[i][j] = 1 (n-i*p-j*sqrt(p)? <= p)

代入一個大數據發現會爆，所以使用高精，高精照樣爆，只好使用壓6位，輸出的時候記得要%06lf，補位！！

#include <cstdio> #include <cmath>long f[1010][1010][60]; const long bit = 1000000;void add(long* a,long* b,long* c) {c[0] = a[0]>b[0]?a[0]:b[0];c[0] ++;for (long i=1;i<c[0]+1;i++){c[i] += a[i]+b[i];if (c[i] > bit-1){c[i] -= bit;c[i+1] ++;}}if (c[c[0]] == 0) c[0]--; }void print(long* a) {printf("%ld",a[a[0]]);for (long i=a[0]-1;i>0;i--){printf("%06ld",a[i]);}printf("\n"); }int main() {freopen("prob.in","r",stdin);freopen("prob.out","w",stdout);long n,p;scanf("%ld%ld",&n,&p);for (long i=(n/p);i>-1;i--){for (long j=long((n/sqrt(p)))+1;j>-1;j--){if (n-(i+1)*p<=0||j*j*p>=n*n+(i+1)*(i+1)*p*p-2*n*p*(i+1)){f[i][j][0] = 1;f[i][j][1] = 1;f[i][j][2] = 0;}else{add(f[i+1][j],f[i][j+1],f[i][j]);}}}print(f[0][0]); }

總結

以上是生活随笔為你收集整理的【动态规划】prob的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。