剛那到題目時以為是搜索題,分析一下又覺得是動歸或者記憶化搜索...
其實都不是的,是一道白癡題.
題目中的陷阱很多, 做男人就是不容易啊,沒有女孩子細心,我竟然為它的每一個陷阱都貢獻了一個以上WA..
以下是題目中較生猛陷阱,需要細心的:
.
The input is terminated by a line with a negative integer (習慣上會認為以-1結束)
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). 這個條件..太強悍了..關于0時是YES還是NO的問題,我貢獻了3個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 ;
}