傳送門

題目描述

對于一個遞歸函數(shù)$w(a,b,c)$
如果$a\le 0a\le 0orb\le 0b\le 0orc\le 0c\le 0$就返回值11.
如果$a>20a>20orb>20b>20orc>20c>20$就返回$w(20,20,20)$
如果$a<ba<b$并且$b<cb<c$ 就返回$w(a,b,c?1)+w(a,b?1,c?1)?w(a,b?1,c)$
其它的情況就返回$w(a?1,b,c)+w(a?1,b?1,c)+w(a?1,b,c?1)?w(a?1,b?1,c?1)$
這是個簡單的遞歸函數(shù)，但實現(xiàn)起來可能會有些問題。當(dāng)$a,b,c$均為15時，調(diào)用的次數(shù)將非常的多。你要想個辦法才行.

/*
比如 w(30,-1,0)w(30,?1,0)既滿足條件1又滿足條件2
這種時候我們就按最上面的條件來算
所以答案為1
*/

輸入格式：
會有若干行。
并以-1,-1,-1結(jié)束。
保證輸入的數(shù)在$[?9223372036854775808,9223372036854775807]$之間，并且是整數(shù)。

輸出格式：
輸出若干行，每一行格式：
$w(a,b,c)=ans$
注意空格。

輸入樣例#1：
1 1 1
2 2 2
-1 -1 -1
輸出樣例#1：
w(1, 1, 1) = 2
w(2, 2, 2) = 4

分析

• 這道題是一道比較基礎(chǔ)的記憶化搜索題目。依照題意，我們只需要開一個每一維都比20稍大的三維數(shù)組保存中間狀態(tài)的值，避免遞歸過程中大量的重復(fù)計算就可以解決這道題了。
• 除此之外，因為數(shù)組下標(biāo)不能為負(fù)，需要注意條件的判斷。避免使用為負(fù)值或者越界的下標(biāo)。

代碼如下

import java.io.BufferedInputStream; import java.util.*; public class Main {static long ws[][][]=new long [25][25][25];static long w(int a,int b,int c) {if(a<=0 || b<=0 || c<=0)return 1;if(ws[a][b][c]==0) {if(a<b && b<c) ws[a][b][c]=w(a, b, c-1)+w(a, b-1, c-1)-w(a, b-1, c); else ws[a][b][c]=w(a-1, b, c)+w(a-1, b-1, c)+w(a-1, b, c-1)-w(a-1, b-1, c-1);}return ws[a][b][c];}public static void main(String[] args) {long a,b,c;Scanner cin=new Scanner(new BufferedInputStream(System.in));while(cin.hasNext()) {a=cin.nextInt();b=cin.nextInt();c=cin.nextInt();if(a==-1&&b==-1&&c==-1)break;if(a<=0 || b<=0 || c<=0) {System.out.println("w("+a+", "+b+", "+c+") = 1");}else if(a>20 || b>20 || c>20) {System.out.println("w("+a+", "+b+", "+c+") = "+w(20, 20, 20));}else {System.out.println("w("+a+", "+b+", "+c+") = "+w((int)a, (int)b, (int)c));}}cin.close();} }

總結(jié)

以上是生活随笔為你收集整理的P1464 Function（递归式的记忆化搜索）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。