請參考swordlance的程序,我這程序還是有問題。
的確因為有減法k的值可能為-1,用-1做判斷不行。。
再開壹個數組來記錄訪問情況是比較好。
開個表遞歸的時候記錄處理過的狀態應該是這題的標準解法,
不過在不超過時限的情況下非遞歸也是能解的。
---------------------------------------------
這題妳直接就遞歸了?
這題明顯有隱含的意思在裏面的,先仔細分析題目再動手寫程序。
下面是我的壹點分析,僅供參考。
a,b,c有壹個小於等於0,結果為1可以直接輸出
a,b,c有壹個大於20,結果為1048576可以直接輸出
下面只需要預處理把
k(1,1,1) ~ k(20,20,20)遞推出來,有了a,b,c直接把k(a,b,c)對應的值輸出即可
試著做了壹下,遞推k的過程可能有點暴力,不過應該不會超時
#include?<iostream>using?namespace?std;
int?main()
{
//預處理:遞推k
int?k[21][21][21];
//初始化k
for(int?i=0;?i<=20;?i++)
{
for(int?j=0;?j<=20;?j++)
{
for(int?r=0;?r<=20;?r++)
{
k[i][j][r]?=?-1;
}
}
}
//abc有0結果為1
for(int?i=0;?i<=20;?i++)
{
for(int?j=0;?j<=20;?j++)
{
k[0][i][j]?=?k[i][0][j]?=?k[i][j][0]?=?1;
}
}
//計算k,直到全部算完(這裏可能有更好的方法)
int?tot?=?0;
while(1)
{
if(tot?>=?8000)?break;
for(int?i=1;?i<=20;?i++)
{
for(int?j=1;?j<=20;?j++)
{
for(int?r=1;?r<=20;?r++)
{
if(i?<?j?&&?j?<?r)
{
if((k[i][j][r-1]?==?-1)?||?(k[i][j-1][r-1]?==?-1)?||?(k[i][j-1][r]?==?-1))?continue;
k[i][j][r]?=?k[i][j][r-1]?+?k[i][j-1][r-1]?-?k[i][j-1][r];
}
else
{
if((k[i-1][j][r]?==?-1)?||?(k[i-1][j-1][r]?==?-1)?||?(k[i-1][j][r-1]?==?-1)?||?(k[i-1][j-1][r-1]?==?-1))?continue;
k[i][j][r]?=?k[i-1][j][r]?+?k[i-1][j-1][r]?+?k[i-1][j][r-1]?-?k[i-1][j-1][r-1];
}
tot++;
}
}
}
}
//直接輸出k[a][b][c]即可
int?a,?b,?c;
cin?>>?a?>>?b?>>?c;
if(a>20?||?b>20?||?c>20)?cout?<<?1048576?<<?endl;
else?if(a?<=?0?||?b?<=?0?||?c?<=?0)?cout?<<?1?<<?endl;
else
{
cout?<<?k[a][b][c]?<<?endl;
}
return?0;
}