剛那到題目時(shí)以為是搜索題,分析一下又覺(jué)得是動(dòng)歸或者記憶化搜索...
其實(shí)都不是的,是一道白癡題.
題目中的陷阱很多, 做男人就是不容易啊,沒(méi)有女孩子細(xì)心,我竟然為它的每一個(gè)陷阱都貢獻(xiàn)了一個(gè)以上WA..
以下是題目中較生猛陷阱,需要細(xì)心的:
.
The input is terminated by a line with a negative integer (習(xí)慣上會(huì)認(rèn)為以-1結(jié)束)
For a given n, you'll check if there are some xi, and let n equal to Σ1<=i<=txi!. (t >=1 1, xi >= 0, xi = xj iff. i = j). 這個(gè)條件..太強(qiáng)悍了..關(guān)于0時(shí)是YES還是NO的問(wèn)題,我貢獻(xiàn)了3個(gè)WA才看清!
代碼如下
:
#include"stdio.h"
int fun(int x)
{
int temp=1;
int y=1;
while(y<=x)
{
temp=temp*y;
y++;
}
return temp;
}
void main()
{
int n;
int i;
int a[12];
for(i=0;i<=11;i++)
a[i]=fun(i);
while(1)
{
scanf("%d",&n);
if(n==0){printf("NO\n");continue;}
if(n<0)return;
i=11;
while(i>=0&&n>=0)
{
if(n>=a[i])n=n-a[i];
i--;
}
if(n==0)printf("YES\n");
else printf("NO\n");
}
return ;
}